Bell polynomials
From Free net encyclopedia
Contents |
Definition
In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are given by
- <math>B_{n,k}(x_1,x_2,\dots,x_{n-k+1})</math>
- <math>=\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}},</math>
the sum extending over all sequences j1, j2, j3, ..., jn−k+1 of non-negative integers such that
- <math>j_1+j_2+\cdots = k\quad\mbox{and}\quad j_1+2j_2+3j_3+\cdots=n.</math>
Convolution identity
For sequences xn, yn, n = 1, 2, ..., define a sort of convolution by
- <math>(x \diamondsuit y)_n = \sum_{j=1}^{n-1} {n \choose j} x_j y_{n-j}</math>
(the bounds of summation are 1 and n − 1, not 0 and n).
Let <math>x_n^{k\diamondsuit}\,</math> be the nth term of the sequence
- <math>\underbrace{x\diamondsuit\cdots\diamondsuit x}_{k\ \mathrm{factors}}.\,</math>
Then
- <math>B_{n,k}(x_1,\dots,x_{n-k+1}) = {x_{n}^{k\diamondsuit} \over k!}.\,</math>
"Complete" Bell polynomials
The sum
- <math>B_n(x_1,\dots,x_n)=\sum_{k=1}^n B_{n,k}(x_1,x_2,\dots,x_{n-k+1})</math>
is sometimes called the nth complete Bell polynomial. In order to contrast them with complete Bell polynomials, the polynomials Bn, k defined above are sometimes called "partial" Bell polynomials. The complete Bell polynomials satisfy the following identity
- <math>B_n(x_1,\dots,x_n) = \det\left[\begin{matrix}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} \\ \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & & \vdots \\ \\ 0 & 0 & 0 & 0 & 0 & \cdots & -1 & x_1 \end{matrix}\right]</math>
Combinatorial meaning
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
For example, we have
- <math>B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_2+10x_3^2</math>
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,
- <math>B_{6,3}(x_1,x_2,x_3,x_4)=15x_4x_1^2+60x_3x_2x_1+15x_2^3</math>
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 Bn,k(x1,x2,...) when all xs are equal to 1 is a Stirling number of the second kind:
- <math>B_{n,k}(1,1,\dots)=S(n,k)=\left\{\begin{matrix} n \\ k \end{matrix}\right\}.</math>
The sum
- <math>\sum_{k=1}^n B_{n,k}(1,1,1,\dots) = \sum_{k=1}^n\left\{\begin{matrix} n \\ k \end{matrix}\right\} </math>
is the nth 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
- <math>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.</math>
Then
- <math>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.</math>
The complete Bell polynomials appear in the exponential of a formal power series:
- <math>\exp\left(\sum_{n=1}^\infty {a_n \over n!} x^n \right)
= 1 + \sum_{n=1}^\infty {B_n(a_1,\dots,a_n) \over n!} x^n.</math>
See also exponential formula.
Moments and cumulants
The sum
- <math>B_n(\kappa_1,\dots,\kappa_n)=\sum_{k=1}^n B_{n,k}(\kappa_1,\dots,\kappa_{n-k+1})</math>
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
For any sequence a1, a2, a3, ... of scalars, let
- <math>p_n(x)=\sum_{k=1}^n B_{n,k}(a_1,\dots,a_{n-k+1}) x^k.</math>
Then this polynomial sequence is of binomial type, i.e. it satisfies the binomial identity
- <math>p_n(x+y)=\sum_{k=0}^n {n \choose k} p_k(x) p_{n-k}(y)</math>
for n ≥ 0. In fact we have this result:
- Theorem: All polynomial sequences of binomial type are of this form.
If we let
- <math>h(x)=\sum_{n=1}^\infty {a_n \over n!} x^n</math>
taking this power series to be purely formal, then for all n,
- <math>h^{-1}\left( {d \over dx}\right) p_n(x) = n p_{n-1}(x).</math>
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.A., 1974.
- Steven Roman, The Umbral Calculus, Dover Publications.