Bell polynomials

Last updated • 9 min readFrom Wikipedia, The Free Encyclopedia

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.

Contents

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, ..., jnk+1 of non-negative integers such that these two conditions are satisfied:

The sum

is called the nth 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, ..., jnk+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 {A, B, C}, it can be partitioned into two non-empty, non-overlapping subsets, which are also referred to as parts or blocks, in 3 different ways:

{{A}, {B, C}}
{{B}, {A, C}}
{{C}, {B, A}}

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 (or block of size i) 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 = 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.

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

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,

because the ways to partition a set of 6 elements as 3 blocks 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.

Table of values

Below is a triangular array of the incomplete Bell polynomials :

k
n
0123456
0
1
2
3
4
5
6

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 , 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. [1]

Recurrence relations

The complete Bell polynomials can be recurrently defined as

with the initial value .

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

where

In addition: [2]

When ,

The complete Bell polynomials also satisfy the following recurrence differential formula: [3]

Derivatives

The partial derivatives of the complete Bell polynomials are given by [4]

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(x1,x2,...) 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 Bn,k(x1,x2,...) 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 nth 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, [5] [6] 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 [2]

For example, let us compute . We have

and thus,

Other identities

This corrects the omission of the factor in Comtet's book. [7]


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 .

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 f0 = 0 and f1 ≠ 0, then an explicit form of the coefficients of the inverse can be given in term of Bell polynomials as [8]

with and is the rising factorial, and

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 and the power sum symmetric polynomial 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 can be expressed in terms of complete Bell polynomials as follows:

Moments and cumulants

The sum

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

Hermite polynomials

Hermite polynomials can be expressed in terms of Bell polynomials as

where xi = 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 a1, a2, …, an of scalars, let

Then this polynomial sequence is of binomial type, i.e. it satisfies the binomial identity

Example: For a1 = … = an = 1, the polynomials 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

then for all n,

Software

Bell polynomials are implemented in:

See also

Notes

  1. Comtet 1974.
  2. 1 2 Cvijović 2011.
  3. Alexeev, Pologova & Alekseyev 2017, sect. 4.2.
  4. Bell 1934, identity (5.1) on p. 266.
  5. Chou, W.-S.; Hsu, Leetsch C.; Shiue, Peter J.-S. (2006-06-01). "Application of Faà di Bruno's formula in characterization of inverse relations". Journal of Computational and Applied Mathematics. 190 (1–2): 151–169. doi: 10.1016/j.cam.2004.12.041 .
  6. Chu, Wenchang (2021-11-19). "Bell Polynomials and Nonlinear Inverse Relations". The Electronic Journal of Combinatorics. 28 (4). doi: 10.37236/10390 . ISSN   1077-8926.
  7. Comtet 1974, identity [3l"] on p. 136.
  8. Charalambides 2002, p. 437, Eqn (11.43).

Related Research Articles

<span class="mw-page-title-main">Binomial coefficient</span> Number of subsets of a given size

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers nk ≥ 0 and is written It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n; this coefficient can be computed by the multiplicative formula

In mathematics, the Bernoulli numbersBn are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

<span class="mw-page-title-main">Taylor series</span> Mathematical approximation of a function

In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor series are equal near this point. Taylor series are named after Brook Taylor, who introduced them in 1715. A Taylor series is also called a Maclaurin series when 0 is the point where the derivatives are considered, after Colin Maclaurin, who made extensive use of this special case of Taylor series in the 18th century.

In mathematics, the Euler numbers are a sequence En of integers defined by the Taylor series expansion

In mathematics, a power series is an infinite series of the form where an represents the coefficient of the nth term and c is a constant called the center of the series. Power series are useful in mathematical analysis, where they arise as Taylor series of infinitely differentiable functions. In fact, Borel's theorem implies that every power series is the Taylor series of some smooth function.

In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in 1782.

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form, by some expression involving operations on the formal series.

In mathematics, the falling factorial is defined as the polynomial

In algebra, the partial fraction decomposition or partial fraction expansion of a rational fraction is an operation that consists of expressing the fraction as a sum of a polynomial and one or several fractions with a simpler denominator.

<span class="mw-page-title-main">Bernstein polynomial</span> Type of polynomial used in Numerical Analysis

In the mathematical field of numerical analysis, a Bernstein polynomial is a polynomial expressed as a linear combination of Bernstein basis polynomials. The idea is named after mathematician Sergei Natanovich Bernstein.

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. Any two probability distributions whose moments are identical will have identical cumulants as well, and vice versa.

Faà di Bruno's formula is an identity in mathematics generalizing the chain rule to higher derivatives. It is named after Francesco Faà di Bruno, although he was not the first to state or prove the formula. In 1800, more than 50 years before Faà di Bruno, the French mathematician Louis François Antoine Arbogast had stated the formula in a calculus textbook, which is considered to be the first published reference on the subject.

In mathematical analysis, Cesàro summation assigns values to some infinite sums that are not necessarily convergent in the usual sense. The Cesàro sum is defined as the limit, as n tends to infinity, of the sequence of arithmetic means of the first n partial sums of the series.

In combinatorial mathematics, the exponential formula states that the exponential generating function for structures on finite sets is the exponential of the exponential generating function for connected structures. The exponential formula is a power series version of a special case of Faà di Bruno's formula.

In combinatorial mathematics, Dobiński's formula states that the th Bell number , the number of partitions of a set of size , equals

<span class="mw-page-title-main">Stirling numbers of the second kind</span> Numbers parameterizing ways to partition a set

In mathematics, particularly in combinatorics, a Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling.

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the unsigned Stirling numbers of the first kind count permutations according to their number of cycles.

<span class="mw-page-title-main">Eulerian number</span> Polynomial sequence

In combinatorics, the Eulerian number is the number of permutations of the numbers 1 to in which exactly elements are greater than the previous element.

In the mathematical field of combinatorics, the q-Pochhammer symbol, also called the q-shifted factorial, is the product with It is a q-analog of the Pochhammer symbol , in the sense that The q-Pochhammer symbol is a major building block in the construction of q-analogs; for instance, in the theory of basic hypergeometric series, it plays the role that the ordinary Pochhammer symbol plays in the theory of generalized hypergeometric series.

In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.

References