Bell polynomials

﻿
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 j1, j2, j3, ..., jnk+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 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 B4,3(x1,x2). 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.$

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 Bnk 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 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

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

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:

$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

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

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 κ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

$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) = n p_{n-1}(x).$

Software

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

• Bell matrix

References

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Bell number — In combinatorial mathematics, the n th Bell number, named in honor of Eric Temple Bell, is the number of partitions of a set with n members, or equivalently, the number of equivalence relations on it. Starting with B 0 = B 1 = 1, the first few… …   Wikipedia

• Eric Temple Bell — Infobox Scientist name = Eric Temple Bell image width = caption = birth date = birth date|1883|2|7|mf=y birth place = Peterhead, Scotland death date = death date and age|1960|12|21|1883|2|7|mf=y death place = Watsonville, California residence =… …   Wikipedia

• Polynômes de Bell — En mathématiques, et plus précisément en combinatoire, les polynômes de Bell, nommés ainsi d après le mathématicien Eric Temple Bell, sont donnés par où la somme porte sur toutes les suites j1, j2, j3, ..., jn−k+1 d entiers naturels tels que …   Wikipédia en Français

• Touchard polynomials — The Touchard polynomials, named after Jacques Touchard, also called the exponential polynomials, comprise a polynomial sequence of binomial type defined by:T n(x)=sum {k=1}^n S(n,k)x^k=sum {k=1}^nleft{egin{matrix} n k end{matrix} ight}x^kwhere S …   Wikipedia

• Binomial type — In mathematics, a polynomial sequence, i.e., a sequence of polynomials indexed by { 0, 1, 2, 3, ... } in which the index of each polynomial equals its degree, is said to be of binomial type if it satisfies the sequence of identities:p n(x+y)=sum… …   Wikipedia

• Cumulant — In probability theory and statistics, the cumulants κn of a probability distribution are a set of quantities that provide an alternative to the moments of the distribution. The moments determine the cumulants in the sense that any two probability …   Wikipedia

• Полиномы Белла — В математике, в частности в комбинаторике, полиномы Белла это полиномы вида где сумма берётся по всем последовательностям j1, j2, j3, ..., jn−k+1 неотрицательных целых чисел таким, что и …   Википедия

• List of special functions and eponyms — This is a list of special function eponyms in mathematics, to cover the theory of special functions, the differential equations they satisfy, named differential operators of the theory (but not intended to include every mathematical eponym).… …   Wikipedia

• List of polynomial topics — This is a list of polynomial topics, by Wikipedia page. See also trigonometric polynomial, list of algebraic geometry topics.Basics*Polynomial *Coefficient *Monomial *Polynomial long division *Polynomial factorization *Rational function *Partial… …   Wikipedia

• Polynomial sequence — In mathematics, a polynomial sequence is a sequence of polynomials indexed by the nonnegative integers 0, 1, 2, 3, ..., in which each index is equal to the degree of the corresponding polynomial. Examples * Monomials * Rising factorials * Falling …   Wikipedia