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 Faà di Bruno's formula and an explicit formula for Lagrange inversion.

Definitions

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 j1, j2, j3,..., jn−''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 is defined by
where the sum runs over all sequences j1, j2, j3,..., jn−''k''+1 of non-negative integers such that
Thanks to the first condition on indices, we can rewrite the formula as
where we have used the multinomial coefficient.
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, it can be partitioned into two non-empty, non-overlapping subsets, which are 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 B3,2 tell us that we are considering the partitioning of a set with 3 elements into 2 blocks. The subscript of each xi indicates the presence of a block with i elements in a given partition. So here, x2 indicates the presence of a block with 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, the fact that both x1 and x2 have exponent 1 indicates that there is only one such block in a given partition. The coefficient of the monomial indicates how many such partitions there are. Here, 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 = x''1n.
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 monomial 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 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, 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.

Examples

For example, we have
because the ways to partition a set of 6 elements as 2 blocks are
Similarly,
because the ways to partition a set of 6 elements as 3 blocks are

Table of values

Below is a triangular array of the incomplete Bell polynomials :
0123456
0------
1-----
2----
3---
4--
5-
6

Properties

Generating functions

The exponential partial Bell polynomials have the following bivariate generating function:
In other words, by what amounts to the same, by the series expansion of the k-th power:
The generating function for the exponential Bell polynomial is given since
Likewise, the generating function for the ordinary partial Bell polynomial is
In particular, by taking the coefficient of, we have:
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 satisfy a recurrence relation:
with the initial value.
The partial Bell polynomials can also be computed efficiently by a recurrence relation:
where
In addition:
When,
The complete Bell polynomials also satisfy the following recurrence differential formula:

Derivatives

The partial derivatives of the complete Bell polynomials are given by
Similarly, the partial derivatives of the partial Bell polynomials are given by
If the arguments of the Bell polynomials are one-dimensional functions, the chain rule can be used to obtain

Stirling numbers and Bell numbers

The value of the Bell polynomial Bn,''k on the sequence of factorials equals an unsigned Stirling number of the first kind:
The sum of these values gives the value of the complete Bell polynomial on the sequence of factorials:
The value of the Bell polynomial B''n,''k on the sequence of ones equals a Stirling number of the second kind:
The sum of these values gives the value of the complete Bell polynomial on the sequence of ones:
which is the n''th Bell number.
which gives the Lah number.

Touchard polynomials

Touchard polynomial can be expressed as the value of the complete Bell polynomial on all arguments being x:

Inverse relations

If we define
then we have the inverse relationship
More generally, given some function admitting an inverse,

Determinant forms

The complete Bell polynomial can be expressed as determinants:
and

Convolution identity

For sequences xn, yn, n = 1, 2,..., define a convolution by:
The bounds of summation are 1 and n − 1, not 0 and n.
Let be the nth term of the sequence
Then
For example, let us compute. We have
and thus,

Other identities

  • which gives the idempotent number.
  • .
  • The complete Bell polynomials satisfy the binomial type relation:
  • :
  • :
  • Special cases of partial Bell polynomials:

    Examples

The first few complete Bell polynomials are:

Applications

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.