Bell polynomials

From Wikipedia, the free encyclopedia
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, is used in the study of set partitions. It is related to Stirling and Bell numbers. It also occurs in many applications, such as in the Faà di Bruno's formula.

Bell polynomials[edit]

Exponential Bell polynomial[edit]

The partial or incomplete exponential Bell polynomials 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 these two conditions are satisfied:

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

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 exponential Bell polynomial. In order to contrast them with complete Bell polynomials, the polynomials Bn,k are sometimes called partial or incomplete Bell polynomials.

Ordinary Bell polynomial[edit]

Likewise, the partial ordinary Bell polynomial, in contrast to the usual exponential Bell polynomial defined above, is given by

\hat{B}_{n,k}(x_1,x_2,\ldots,x_{n-k+1}) = \sum \frac{k!}{j_1! j_2! \cdots j_{n-k+1}!} x_1^{j_1} x_2^{j_2} \cdots x_{n-k+1}^{j_{n-k+1}},

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

j_1 + j_2 + \cdots + j_{n-k+1} = k,
j_1 + 2 j_2 + \cdots + (n-k+1)j_{n-k+1} = n.

In general, Bell polynomial refers to the exponential Bell polynomial, unless otherwise explicitly stated.

Combinatorial meaning[edit]

The exponential Bell polynomial encodes the information related to the ways a set can be partitioned. For example, if we consider a set {A,B,C}, it can partitioned into two non-empty, non-overlapping subsets, which is also referred to as parts or blocks, in 3 different ways:


Thus, we can encode the information regarding these partitions as

B_{3,2}(x_1,x_2) = 3 x_1 x_2.

Here, the subscripts of B3,2 tells us that we are considering the partitioning of set with 3 elements into 2 blocks. The subscript of each xi indicates the presence of block with i elements (or block of size i) in a given partition. So here, x2 indicates the presence of a block with a two elements. Similarly, x1 indicates the presence of a block with a single element. The exponent of xij indicates that there are j such blocks of size i in a single partition. Here, since both x1 and x2 has exponent 1, it indicates there there is only one such block in a given partition. The coefficient of the monomial indicates how many such partitions there are. For our case, there are 3 partitions of a set with 3 elements into 2 blocks, where in each partition the elements are divided into two blocks of sizes 1 and 2.

Since any set can be divided into a single block in only one way, the above interpretation would mean that Bn,1 = xn. Similarly, since there is only one way that a set with n elements be divided into n singletons, Bn,n = x1n.

As a more complicated example, consider


This tells us that if a set with 6 elements is divided into 2 blocks, then we can have 6 partitions with blocks of size 1 and 5, 15 partitions with blocks of size 4 and 2, and 10 partitions with 2 blocks of size 3.

Note that the sum of the subscripts in a monomials is equal to the total number of elements. Thus, the number of monomials that appear in the partial Bell polynomial is equal to the number of ways the integer n can be expressed as a summation of k positive integers. This is the same as the integer partition of n into k parts. For instance, in the above examples, the integer 3 can be partitioned into two parts as 2+1 only. Thus, there is only one monomial in B3,2. However, the integer 6 can be partitioned into two parts as 5+1, 4+2, and 3+3. Thus, there are three monomials in B6,2. Indeed, the subscripts of the variables in a monomial are the same those given by the integer partition, indicating the sizes of the different blocks. The total number of monomials appearing in a complete Bell polynomial Bn is thus the same by the total integer partition of n.

Also note that the degree of each monomial, which is the sum of the exponents of each variable in the monomial, is equal to the number of blocks the set is divided into. That is, j1 + j2 + ... = k . Thus, given a complete Bell polynomial Bn, we can separate the partial Bell polynomial Bn,k by collecting all those monomials with degree k.

Finally, if we disregard the sizes of the blocks and put all xi = x, then the summation of the coefficients of the partial Bell polynomial Bn,k will give the total number of ways that a set with n elements can be partitioned into k blocks, which is the same as the Stirling numbers of the second kind. Also, the summation of all the coefficients of the complete Bell polynomial Bn will give us the total number of ways a set with n elements can be partitioned into non-overlapping subsets, which is the same as the Bell number.

In general, 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.


For example, we have


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.



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.


Generating function[edit]

The complete exponential Bell polynomial can be equivalently defined by its exponential generating function:

 \exp\left( \sum_{j=1}^\infty x_j \frac{t^j}{j!} \right) = \sum_{n=0}^\infty B_n(x_1,\ldots, x_n) \frac{t^n}{n!}.

Thus, the n-th complete Bell polynomial is given by

 B_n(x_1,\ldots, x_n) = \frac{\mathrm{d}^n}{\mathrm{d} t^n} \exp\left( \sum_{j=1}^\infty x_j \frac{t^j}{j!} \right) \Big|_{t=0}.

Recurrence relation[edit]

The complete Bell polynomials can be recursively defined as,

 B_{n+1}(x_1, \ldots, x_{n+1}) = \sum_{i=0}^n {n \choose i} B_{n-i}(x_1, \ldots, x_{n-i}) x_{i+1},

with the initialization B_0 = 1.

The partial Bell polynomials can also be computed efficiently by a recursion relation

 B_{n,k} = \sum_{i=1}^{n-k+1} \binom{n-1}{i-1} x_{i} B_{n-i,k-1}

where  B_{0,0} = 1;  B_{n,0} = 0 \; \mathrm{for} \; n \geq 1;  B_{0,k} = 0 \; \mathrm{for} \; k \geq 1.

Determinant form[edit]

The complete Bell polynomial can be expressed as a determinant, as given by

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

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)=|s(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.

Inverse relations[edit]

If we define

y_n = \sum_{k=1}^n B_{n,k}(x_1,\ldots,x_{n-k+1}),

then we have the inverse relationship

x_n = \sum_{k=1}^n (-1)^{k-1} (k-1)! B_{n,k}(y_1,\ldots,y_{n-k+1}).

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}}.\,


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.

Other identities[edit]

  • B_{n,k}(1!,2!,\ldots,(n-k+1)!) = \binom{n-1}{k-1} \frac{n!}{k!} = L(n,k) which gives the Lah number
  • B_{n,k}(1,2,3,\ldots,n-k+1) = \binom{n}{k} k^{n-k} which gives the Idempotent number


The first few complete Bell polynomials are:

 B_1(x_1) = x_1,
 B_2(x_1,x_2) = x_1^2 + x_2,
 B_3(x_1,x_2,x_3) = x_1^3 + 3x_1 x_2 + x_3,
 B_4(x_1,x_2,x_3,x_4) = x_1^4 + 6 x_1^2 x_2 + 4 x_1 x_3 + 3 x_2^2 + x_4,
 B_5(x_1,x_2,x_3,x_4,x_5) = x_1^5 + 10 x_2 x_1^3 + 15 x_2^2 x_1 + 10 x_3 x_1^2 + 10 x_3 x_2 + 5 x_4 x_1 + x_5
 B_6(x_1,x_2,x_3,x_4,x_5,x_6) = x_1^6 + 15 x_2 x_1^4 + 20 x_3 x_1^3 + 45 x_2^2 x_1^2 + 15 x_2^3 + 60 x_3 x_2 x_1 + 15 x_4 x_1^2 + 10 x_3^2 + 15 x_4 x_2 + 6 x_5 x_1 + x_6.


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.


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,

which also represents the exponential generating function of the complete Bell polynomials on a fixed sequence of arguments a_1, a_2, \dots.

Reversion of series[edit]

Let two functions f and g be expressed in formal power series as

f(w) = \sum_{k=0}^\infty f_k \frac{w^k}{k!}, \qquad \mathrm{and}  \qquad  g(z) = \sum_{k=0}^\infty g_k \frac{z^k}{k!},

such that g is the compositional inverse of f defined by g(f(w)) = w or f(g(z)) = z. If f0 = 0 and f1 ≠ 0, then an explicit form of the coefficients of the inverse can be given in term of Bell polynomials as [1]

 g_n = \frac{1}{f_1^n} \sum_{k=1}^{n-1} (-1)^k n^{\bar{k}} B_{n-1,k}(\hat{f}_1,\hat{f}_2,\ldots,\hat{f}_{n-k}), \qquad n \geq 2,

with  \hat{f}_k = \frac{f_{k+1}}{(k+1)f_{1}}, and n^{\bar{k}} = n(n+1)\cdots (n+k-1) is the rising factorial, and g_1 = \frac{1}{f_{1}}.

Asymptotic expansion of Laplace-type integrals[edit]

Consider the integral of the form

I(\lambda) = \int_a^b e^{-\lambda f(x)} g(x) \mathrm{d}x,

where (a,b) is a real (finite or infinite) interval, λ is a large positive parameter and the functions f and g are continuous. Let f have a single minima in [a,b] which occur at x=a. Assume that as x→a+,

 f(x) \sim f(a) + \sum_{k=0}^\infty a_k (x-a)^{k+\alpha},
 g(x) \sim \sum_{k=0}^\infty b_k (x-a)^{k+\beta-1},

with α > 0, Re(β) > 0; and that the expansion of f can be term wise differentiated. Then, Laplace-Erdelyi theorem states that the asymptotic expansion of the integral I(λ) is given by

 I(\lambda) \sim e^{-\lambda f(a)} \sum_{n=0}^\infty \Gamma \Big(\frac{n+\beta}{\alpha} \Big) \frac{c_n}{\lambda^{(n+\beta)/\alpha}} \qquad \mathrm{as} \quad \lambda \rightarrow \infty,

where the coefficients cn are expressible in terms of an and bn using partial ordinary Bell polynomials, as given by Campbell-Froman-Walles-Wojdylo formula:

 c_n = \frac{1}{\alpha a_0^{(n+\beta)/\alpha}} \sum_{k=0}^n b_{n-k} \sum_{j=0}^k \binom{-\frac{n+\beta}{\alpha}}{j} \frac{1}{a_0^j} \hat{B}_{k,j}(a_1,a_2,\ldots,a_{k-j+1}).

Cycle index of symmetric groups[edit]

Main article: Cycle index

The cycle index of the symmetric group S_n can be expressed in terms of complete Bell polynomials as follows:

 Z(S_n) = \frac{B_n(0!\,a_1, 1!\,a_2, \dots, (n-1)!\,a_n)}{n!}.

Moments and cumulants[edit]

The sum

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

is the nth raw 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. Likewise, the nth cumulant can be given in terms of the moments as

\kappa_n = \sum_{k=1}^n (-1)^{k-1} (k-1)! B_{n,k}(\mu'_1,\ldots,\mu'_{n-k+1}).

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) represent 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).


Bell polynomials are implemented in:

See also[edit]


  1. ^ Eqn (11.43), p. 437, C.A. Charalambides, Enumerative Combinatorics, Chapman & Hall / CRC, 2002