Bell polynomials

From Wikipedia, the free encyclopedia
  (Redirected from Bell polynomial)
Jump to: navigation, search
For a different family of polynomials Bn(x) occasionally called Bell polynomials, see Touchard polynomials.

In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are a triangular array of polynomials given by

B_{n,k}(x_1,x_2,\dots,x_{n-k+1})
=\sum{n! \over j_1!j_2!\cdots j_{n-k+1}!}
\left({x_1\over 1!}\right)^{j_1}\left({x_2\over 2!}\right)^{j_2}\cdots\left({x_{n-k+1} \over (n-k+1)!}\right)^{j_{n-k+1}},

where the sum is taken over all sequences j1, j2, j3, ..., jnk+1 of non-negative integers such that

j_1+j_2+\cdots + j_{n-k+1}= k\quad\mbox{and}\quad j_1+2j_2+3j_3+\cdots + (n-k+1)j_{n-k+1}=n.

Complete Bell polynomials[edit]

The sum

B_n(x_1,\dots,x_n)=\sum_{k=1}^n B_{n,k}(x_1,x_2,\dots,x_{n-k+1})

is sometimes called the nth complete Bell polynomial. In order to contrast them with complete Bell polynomials, the polynomials Bn,k are sometimes called partial or incomplete Bell polynomials.

The complete Bell polynomials satisfy the following identity

B_n(x_1,\dots,x_n) = \det\begin{bmatrix}x_1 & {n-1 \choose 1} x_2 & {n-1 \choose 2}x_3 & {n-1 \choose 3} x_4 & {n-1 \choose 4} x_5 & \cdots & \cdots & x_n \\  \\
-1 & x_1 & {n-2 \choose 1} x_2 & {n-2 \choose 2} x_3 & {n-2 \choose 3} x_4 & \cdots & \cdots & x_{n-1} \\  \\
0 & -1 & x_1 & {n-3 \choose 1} x_2 & {n-3 \choose 2} x_3 & \cdots & \cdots & x_{n-2} \\  \\
0 & 0 & -1 & x_1 & {n-4 \choose 1} x_2 & \cdots  & \cdots & x_{n-3} \\  \\
0 & 0 & 0 & -1 & x_1 & \cdots & \cdots & x_{n-4} \\  \\
0 & 0 & 0 & 0 & -1 & \cdots & \cdots & x_{n-5} \\  \\
\vdots & \vdots & \vdots &  \vdots & \vdots & \ddots & \ddots & \vdots  \\  \\
0 & 0 & 0 & 0 & 0 & \cdots & -1 & x_1  \end{bmatrix}.

Combinatorial meaning[edit]

If the integer n is partitioned into a sum in which "1" appears j1 times, "2" appears j2 times, and so on, then the number of partitions of a set of size n that collapse to that partition of the integer n when the members of the set become indistinguishable is the corresponding coefficient in the polynomial.

Examples[edit]

For example, we have

B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_2+10x_3^2

because there are

6 ways to partition a set of 6 as 5 + 1,
15 ways to partition a set of 6 as 4 + 2, and
10 ways to partition a set of 6 as 3 + 3.

Similarly,

B_{6,3}(x_1,x_2,x_3,x_4)=15x_4x_1^2+60x_3x_2x_1+15x_2^3

because there are

15 ways to partition a set of 6 as 4 + 1 + 1,
60 ways to partition a set of 6 as 3 + 2 + 1, and
15 ways to partition a set of 6 as 2 + 2 + 2.

Properties[edit]

  • B_{n,k}(1!,2!,\dots,(n-k+1)!) = \binom{n}{k}\binom{n-1}{k-1} (n-k)!

Stirling numbers and Bell numbers[edit]

The value of the Bell polynomial Bn,k(x1,x2,...) on the sequence of factorials equals an unsigned Stirling number of the first kind:

B_{n,k}(0!,1!,\dots,(n-k)!)=c(n,k)=\left[{n\atop k}\right].

The value of the Bell polynomial Bn,k(x1,x2,...) on the sequence of ones equals a Stirling number of the second kind:

B_{n,k}(1,1,\dots,1)=S(n,k)=\left\{{n\atop k}\right\}.

The sum of these values gives the value of the complete Bell polynomial on the sequence of ones:

B_n(1,1,\dots,1)=\sum_{k=1}^n B_{n,k}(1,1,\dots,1) = \sum_{k=1}^n \left\{{n\atop k}\right\},

which is the nth Bell number.

Touchard polynomials[edit]

Main article: Touchard polynomials

Touchard polynomial T_n(x) = \sum_{k=0}^n \left\{{n\atop k}\right\}\cdot x^k can be expressed as the value of the complete Bell polynomial on all arguments being x:

T_n(x) = B_n(x,x,\dots,x).

Convolution identity[edit]

For sequences xn, yn, n = 1, 2, ..., define a sort of convolution by:

(x \diamondsuit y)_n = \sum_{j=1}^{n-1} {n \choose j} x_j y_{n-j}.

Note that the bounds of summation are 1 and n − 1, not 0 and n .

Let x_n^{k\diamondsuit}\, be the nth term of the sequence

\displaystyle\underbrace{x\diamondsuit\cdots\diamondsuit x}_{k\ \mathrm{factors}}.\,

Then

B_{n,k}(x_1,\dots,x_{n-k+1}) = {x_{n}^{k\diamondsuit} \over k!}.\,

For example, let us compute  B_{4,3}(x_1,x_2) . We have

 x = ( x_1 \ , \ x_2 \ , \ x_3 \ , \ x_4 \ , \dots )
 x \diamondsuit x = ( 0,\  2 x_1^2 \ ,\  6 x_1 x_2 \ , \  8 x_1 x_3 + 6 x_2^2 \ , \dots )
 x \diamondsuit x \diamondsuit x = (  0 \ ,\ 0 \  , \ 6 x_1^3 \ , \ 36 x_1^2 x_2 \ , \dots )

and thus,

 B_{4,3}(x_1,x_2) = \frac{ ( x \diamondsuit x \diamondsuit x)_4 }{3!} = 6 x_1^2 x_2.

Applications[edit]

Faà di Bruno's formula[edit]

Faà di Bruno's formula may be stated in terms of Bell polynomials as follows:

{d^n \over 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).

Similarly, a power-series version of Faà di Bruno's formula may be stated using Bell polynomials as follows. Suppose

f(x)=\sum_{n=1}^\infty {a_n \over n!} x^n \qquad
\mathrm{and} \qquad g(x)=\sum_{n=1}^\infty {b_n \over n!} x^n.

Then

g(f(x)) = \sum_{n=1}^\infty
{\sum_{k=1}^{n} b_k B_{n,k}(a_1,\dots,a_{n-k+1}) \over n!} x^n.

In particular, the complete Bell polynomials appear in the exponential of a formal power series:

\exp\left(\sum_{n=1}^\infty {a_n \over n!} x^n \right)
= \sum_{n=0}^\infty {B_n(a_1,\dots,a_n) \over n!} x^n.

Moments and cumulants[edit]

The sum

B_n(\kappa_1,\dots,\kappa_n)=\sum_{k=1}^n B_{n,k}(\kappa_1,\dots,\kappa_{n-k+1})

is the nth moment of a probability distribution whose first n cumulants are κ1, ..., κn. In other words, the nth moment is the nth complete Bell polynomial evaluated at the first n cumulants.

Representation of polynomial sequences of binomial type[edit]

For any sequence a1, a2, …, an of scalars, let

p_n(x)=\sum_{k=1}^n B_{n,k}(a_1,\dots,a_{n-k+1}) x^k.

Then this polynomial sequence is of binomial type, i.e. it satisfies the binomial identity

p_n(x+y)=\sum_{k=0}^n {n \choose k} p_k(x) p_{n-k}(y).
Example: For a1 = … = an = 1, the polynomials p_n(x) are called Touchard polynomials.

More generally, we have this result:

Theorem: All polynomial sequences of binomial type are of this form.

If we define a formal power series

h(x)=\sum_{k=1}^\infty {a_k \over k!} x^k,

then for all n,

h^{-1}\left( {d \over dx}\right) p_n(x) = n p_{n-1}(x).

Software[edit]

Bell polynomials are implemented in:

See also[edit]

References[edit]