Bell polynomials

In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are used in the study of set partitions. They are related to Stirling and Bell numbers. They also occur in many applications, such as in the Faà di Bruno's formula.
Bell polynomials.
Exponential Bell polynomials.
The "partial" or "incomplete" exponential Bell polynomials are a triangular array of polynomials given by
where the sum is taken over all sequences "j"1, "j"2, "j"3, ..., "j""n"−"k"+1 of non-negative integers such that these two conditions are satisfied:
The sum
is called the "n"th complete exponential Bell polynomial.
Ordinary Bell polynomials.
Likewise, the partial "ordinary" Bell polynomial, in contrast to the usual exponential Bell polynomial defined above, is given by
where the sum runs over all sequences "j"1, "j"2, "j"3, ..., "j""n"−"k"+1 of non-negative integers such that
The ordinary Bell polynomials can be expressed in the terms of exponential Bell polynomials:
In general, Bell polynomial refers to the exponential Bell polynomial, unless otherwise explicitly stated.
Combinatorial meaning.
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 be 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
Here, the subscripts of "B"3,2 tells us that we are considering the partitioning of set with 3 elements into 2 blocks. The subscript of each "x"i indicates the presence of block with "i" elements (or block of size "i") in a given partition. So here, "x"2 indicates the presence of a block with two elements. Similarly, "x"1 indicates the presence of a block with a single element. The exponent of "x"ij indicates that there are "j" such blocks of size "i" in a single partition. Here, since both "x"1 and "x"2 has exponent 1, it indicates that 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 "B""n",1 = "x""n". Similarly, since there is only one way that a set with "n" elements be divided into "n" singletons, "B""n","n" = "x"1"n".
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.
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 "B"3,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 "B"6,2. Indeed, the subscripts of the variables in a monomial are the same as 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 equal to the total number of integer partitions of "n".
Also 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, "j"1 + "j"2 + ... = "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 "x""i" = "x", then the summation of the coefficients of the partial Bell polynomial "B""n","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 "j"1 times, "2" appears "j"2 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
because there are
Similarly,
because there are
Properties.
Generating function.
The exponential partial Bell polynomials can be defined by the double series expansion of its generating function:
In other words, by what amounts to the same, by the series expansion of the "k"-th power:
The complete exponential Bell polynomial is defined by formula_15, or in other words:
Thus, the "n"-th complete Bell polynomial is given by
Likewise, the "ordinary" partial Bell polynomial can be defined by the generating function
Or, equivalently, by series expansion of the "k"-th power:
See also generating function transformations for Bell polynomial generating function expansions of compositions of sequence generating functions and powers, logarithms, and exponentials of a sequence generating function. Each of these formulas is cited in the respective sections of Comtet.
Recurrence relations.
The complete Bell polynomials can be recurrently defined as
with the initial value formula_21.
The partial Bell polynomials can also be computed efficiently by a recurrence relation:
where
The complete Bell polynomials also satisfy the following recurrence differential formula:
Determinant forms.
The complete Bell polynomial can be expressed as determinants:
and
Stirling numbers and Bell numbers.
The value of the Bell polynomial "B""n","k"("x"1,"x"2...) on the sequence of factorials equals an unsigned Stirling number of the first kind:
The value of the Bell polynomial "B""n","k"("x"1,"x"2...) on the sequence of ones equals a Stirling number of the second kind:
Examples.
The first few complete Bell polynomials are:
Applications.
Faà di Bruno's formula.
Faà di Bruno's formula may be stated in terms of Bell polynomials as follows:
Similarly, a power-series version of Faà di Bruno's formula may be stated using Bell polynomials as follows. Suppose
Then
In particular, the complete Bell polynomials appear in the exponential of a formal power series:
which also represents the exponential generating function of the complete Bell polynomials on a fixed sequence of arguments formula_40.
Reversion of series.
Let two functions "f" and "g" be expressed in formal power series as
such that "g" is the compositional inverse of "f" defined by "g"("f"("w")) = "w" or "f"("g"("z")) = "z". If "f"0 = 0 and "f"1 ≠ 0, then an explicit form of the coefficients of the inverse can be given in term of Bell polynomials as
with formula_43 and formula_44 is the rising factorial, and formula_45
Asymptotic expansion of Laplace-type integrals.
Consider the integral of the form
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 minimum in ["a","b"] which occurs at "x" = "a". Assume that as "x" → "a"+,
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
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:
Symmetric polynomials.
The elementary symmetric polynomial formula_51 and the power sum symmetric polynomial formula_52 can be related to each other using Bell polynomials as:
These formulae allow one to express the coefficients of monic polynomials in terms of the Bell polynomials of its zeroes. For instance, together with Cayley–Hamilton theorem they lead to expression of the determinant of a "n" × "n" square matrix "A" in terms of the traces of its powers: 
Cycle index of symmetric groups.
The cycle index of the symmetric group formula_56 can be expressed in terms of complete Bell polynomials as follows:
Moments and cumulants.
The sum
is the "n"th raw moment of a probability distribution whose first "n" cumulants are "κ"1, ..., "κ""n". In other words, the "n"th moment is the "n"th complete Bell polynomial evaluated at the first "n" cumulants. Likewise, the "n"th cumulant can be given in terms of the moments as
Hermite polynomials.
The probabilists' Hermite polynomials can be expressed in terms of Bell polynomials as
where "x""i" = 0 for all "i" > 2; thus allowing for a combinatorial interpretation of the coefficients of the Hermite polynomials. This can be seen by comparing the generating function of the Hermite polynomials
with that of Bell polynomials.
Representation of polynomial sequences of binomial type.
For any sequence "a"1, "a"2, …, "a""n" of scalars, let
Then this polynomial sequence is of binomial type, i.e. it satisfies the binomial identity
More generally, we have this result:
If we define a formal power series
then for all "n",
Software.
Bell polynomials are implemented in: