Partial Bell polynomials $B_{n,k}$

edit · history · discussion · files · long url · combinatorics polynomial

Numbers

$n$

$k$

x1^2

3*x1*x2

x1^3

3*x2^2 + 4*x1*x3

6*x1^2*x2

x1^4

10*x2*x3 + 5*x1*x4

15*x1*x2^2 + 10*x1^2*x3

10*x1^3*x2

x1^5

10*x3^2 + 15*x2*x4 + 6*x1*x5

15*x2^3 + 60*x1*x2*x3 + 15*x1^2*x4

45*x1^2*x2^2 + 20*x1^3*x3

15*x1^4*x2

x1^6

35*x3*x4 + 21*x2*x5 + 7*x1*x6

105*x2^2*x3 + 70*x1*x3^2 + 105*x1*x2*x4 + 21*x1^2*x5

105*x1*x2^3 + 210*x1^2*x2*x3 + 35*x1^3*x4

105*x1^3*x2^2 + 35*x1^4*x3

21*x1^5*x2

x1^7

Definition

For integers $1 \leq k \leq n$ the partial (or incomplete) Bell polynomial $B_{n,k}(x_1, \dots, x_{n-k+1})$ is the polynomial whose coefficient of $x_1^{j_1} x_2^{j_2}\cdots$ is the number of ways to partition a set of $n$ labelled elements into $k$ blocks, exactly $j_i$ of them of size $i$.

Parameters

$n$

— integer ($1 \leq n \leq 7$)

$k$

— integer ($1 \leq k \leq n$)

Formulas

(1)

$B_{n,k}(x_1, \dots, x_{n-k+1}) = \sum \frac{n!}{j_1!\,j_2!\cdots} \left(\frac{x_1}{1!}\right)^{j_1} \left(\frac{x_2}{2!}\right)^{j_2}\cdots$, the sum taken over all sequences $j_1, j_2, \dots$ of non-negative integers with $j_1 + j_2 + \cdots = k$ and $j_1 + 2j_2 + 3j_3 + \cdots = n$.

(2)

Setting every $x_i = 1$ gives the Stirling number of the second kind: $B_{n,k}(1, 1, \dots) = S(n,k)$, and summing over $k$ gives the Bell number $B_n$.

(3)

Setting $x_i = i!$ gives the Lah number [4]: $B_{n,k}(1!, 2!, \dots) = \binom{n-1}{k-1}\frac{n!}{k!}$.

(4)

$B_{n,1}(x_1, \dots, x_n) = x_n$ and $B_{n,n}(x_1) = x_1^{n}$.

(5)

$B_{n,k}$ is homogeneous of degree $k$ in the variables, and every term has weight $n$ when $x_i$ is counted with weight $i$.

(6)

$\frac{d^n}{dx^n} f(g(x)) = \sum_{k=1}^{n} f^{(k)}(g(x))\, B_{n,k}\!\left(g'(x), g''(x), \dots, g^{(n-k+1)}(x)\right)$, which is Faa di Bruno's formula [3] and the reason these polynomials are usually met.

(7)

The complete Bell polynomial is $B_n = \sum_{k=1}^{n} B_{n,k}$.

Comments

(8)

The Bell polynomials in a single variable are a different family: they are the Touchard polynomials Touchard_polynomials, and $T_n(x) = \sum_{k} S(n,k) x^k$ rather than a polynomial in $x_1, x_2, \dots$.

(9)

The table stops at $n = 7$ because of the variables rather than the size. Search matches polynomials that differ only in the names of their variables, which needs a key invariant under renaming, and that key is found by trying permutations; polynomials in more than six variables are refused rather than searched factorially. $B_{n,k}$ involves $x_1$ up to $x_{n-k+1}$, so the first entry over the limit is $B_{8,2}$ with seven. Stopping here keeps every entry of every row.

(10)

The variables are written $x_1, x_2, \dots$, indexed from one as the notation has them, rather than from zero as some computer algebra does. An entry in $B_{n,k}$ involves $x_1$ up to $x_{n-k+1}$, so the number of variables grows as $k$ falls; $B_{n,1}$ is the single term $x_n$ and $B_{n,n}$ is $x_1^n$.

Programs

(P1)

Sage

def partial_bell(n, k):
    #Sage names the variables x0, x1, ...; this database writes them
    #x1, x2, ... as the notation has them.
    p = bell_polynomial(n, k)
    R = PolynomialRing(ZZ, ['x%d' % (i + 1) for i in range(n - k + 1)])
    return R(p.subs({g: R.gen(i) for i, g in enumerate(p.parent().gens())}))

partial_bell(17, 8)              # past the end of this table

Links

[1]

Wikipedia: Bell polynomials

[2]

MathWorld: Bell Polynomial

[3]

Wikipedia: Faa di Bruno's formula

[4]

Wikipedia: Lah number

Data properties

Entries are of type: integral polynomial

Table is complete: false

How well the digits are known: exact