BELL POLYNOMIALS

Contents

Definition

Convolution identity

"Complete" Bell polynomials

Combinatorial meaning

Examples

Stirling numbers and Bell numbers

Where do Bell polynomials occur?

Composition of formal power series and Faà di Bruno's formula

Moments and cumulants

Representation of polynomial sequences of binomial type

References

Definition

In combinatorial mathematics, the 'Bell polynomials', named in honor of Eric Temple Bell, are 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_1over 1!}
ight)^{j_1}left({x_2over 2!}
ight)^{j_2}cdotsleft({x_{n-k+1} over (n-k+1)!}
ight)^{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\; =\; kquadmbox\{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\}$
(the bounds of summation are 1 and ''n'' − 1, not 0 and ''n'').
Let $x\_n^\{kdiamondsuit\},$ be the ''n''th term of the sequence
:$displaystyleunderbrace\{xdiamondsuitcdotsdiamondsuit\; x\}\_\{k\; mathrm\{factors\}\}.,$
Then
:$B\_\{n,k\}(x\_1,dots,x\_\{n-k+1\})\; =\; \{x\_\{n\}^\{kdiamondsuit\}\; over\; k!\}.,$

"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 ''n''th '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
:
-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} \ \
dots & dots & dots & dots & dots & ddots & & dots \ \
0 & 0 & 0 & 0 & 0 & cdots & -1 & x_1 end{matrix}
ight]

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\_5x\_1+15x\_4x\_2+10x\_3^2$
because there are
:6 ways to partition of set of 6 as 5+1,
:15 ways to partition of 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.

Stirling numbers and Bell numbers

The value of the Bell polynomial ''B''_''n'',''k''(''x''₁,''x''₂,...) when all ''x''s are equal to 1 is a Stirling number of the second kind:
:
ight}.
The sum
:
ight}
is the ''n''th Bell number, which is the number of partitions of a set of size ''n''.

Where do Bell polynomials occur?

Composition of formal power series and Faà di Bruno's formula

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:
:$expleft(sum\_\{n=1\}^infty\; \{a\_n\; over\; n!\}\; x^n$
ight)
= 1 + sum_{n=1}^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 ''n''th moment of a probability distribution whose first ''n'' cumulants are κ₁, ..., κ_''n''. In other words, the ''n''th moment is the ''n''th 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\}$
ight) p_n(x) = n p_{n-1}(x).

References

★ Eric Temple Bell, "Partition Polynomials", ''Annals of Mathematics'', volume 29, 1927, pages 38 - 46.

★ Louis Comtet ''Advanced Combinatorics: The Art of Finite and Infinite Expansions'', Reidel Publishing Company, Dordrecht-Holland/Boston-U.S., 1974.

★ Steven Roman, ''The Umbral Calculus'', Dover Publications.