Bell 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}},$

the sum extending over all sequences j₁, j₂, j₃, ..., j_n−k+1 of non-negative integers such that

$j_{1}+j_{2}+\cdots =k\quad {\mbox{and}}\quad j_{1}+2j_{2}+3j_{3}+\cdots =n.$

Convolution identity

For sequences x_n, y_n, 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,\ 2x_{1}^{2}\ ,\ 6x_{1}x_{2}\ ,\ 8x_{1}x_{3}+6x_{2}^{2}\ ,\dots )$

$x\diamondsuit x\diamondsuit x=(\ 0\ ,\ 0\ ,\ 6x_{1}^{3}\ ,\ 36x_{1}^{2}x_{2}\ ,\dots )$

and thus,

$B_{4,3}(x_{1},x_{2})={\frac {(x\diamondsuit x\diamondsuit x)_{4}}{3!}}=6x_{1}^{2}x_{2}.$

Complete Bell polynomials

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 B_n, k defined above are sometimes called "partial" 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

If the integer n is partitioned into a sum in which "1" appears j₁ times, "2" appears j₂ 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

For example, we have

$B_{6,2}(x_{1},x_{2},x_{3},x_{4},x_{5})=6x_{5}x_{1}+15x_{4}x_{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_{4}x_{1}^{2}+60x_{3}x_{2}x_{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.

Stirling numbers and Bell numbers

The value of the Bell polynomial B_n,k(x₁,x₂,...) when all xs are equal to 1 is a Stirling number of the second kind:

$B_{n,k}(1,1,\dots )=S(n,k)=\left\{{\begin{matrix}n\\k\end{matrix}}\right\}.$

The sum

$\sum _{k=1}^{n}B_{n,k}(1,1,1,\dots )=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$

is the nth Bell number, which is the number of partitions of a set of size n.

Properties

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

Applications of Bell polynomials

Faà di Bruno's formula

Main article: Faà di Bruno's formula

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=0}^{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}.$

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}.$

See also exponential formula.

Moments and cumulants

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 κ₁, ..., κ_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

For any sequence a₁, a₂, a₃, ... 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)$

for n ≥ 0. In fact we have this result:

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

If we let

$h(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}$

taking this power series to be purely formal, then for all n,

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

Software available

• Bell polynomials, complete Bell polynomials and generalized Bell polynomials are implemented in Mathematica as BellY.

References

• Eric Temple Bell (1927–1928). "Partition Polynomials". Annals of Mathematics. 29 (1/4): 38–46. doi:10.2307/1967979. MR1502817.
• Louis Comtet (1974). Advanced Combinatorics: The Art of Finite and Infinite Expansions. Dordrecht, Holland / Boston, U.S.: Reidel Publishing Company.
• Steven Roman. The Umbral Calculus. Dover Publications.
• Khristo N. Boyadzhiev (2009). "Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals". Abstract and Applied Analysis. 2009: Article ID 168672. doi:10.1155/2009/168672.{{cite journal}}: CS1 maint: unflagged free DOI (link) (contains also elementary review of the concept Bell-polynomials)
• Silvia Noschese, Paolo E. Ricci (2003). "Differentiation of Multivariable Composite Functions and Bell Polynomials". Journal of Computational Analysis and Applications. 5: 333–340. doi:10.1023/A:1023227705558. '

See also

• Bell matrix