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 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, in contrast to the usual exponential Bell polynomial defined above, is given by

where the sum runs over all sequences j1, j2, j3, ..., jnk+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:

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

Examples

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.

Similarly,

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.

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 exponential:

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 exponential

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 .

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:[1]

Determinant form

The complete Bell polynomial can be expressed as a determinant:

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

Inverse relations

If we define

then we have the inverse relationship

Touchard polynomials

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

Convolution identity

For sequences xn, yn, n = 1, 2, ..., define a sort of convolution by:

Note that 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 Lah number.
  • which gives the idempotent number.
  • The complete Bell polynomials satisfy the binomial type relation:

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[2]

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

The probabilists' 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. ^ Alexeev, Pologova & Alekseyev 2017, sect. 4.2.
  2. ^ Charalambides 2002, p. 437, Eqn (11.43).

References

  • Abbas, M.; Bouroubi, S. (2005). "On new identities for Bell's polynomial". Discrete Math. 293: 5–10. doi:10.1016/j.disc.2004.08.023. MR 2136048.
  • Alexeev, N.; Pologova, A.; Alekseyev, M. A. (2017). "Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs". Journal of Computational Biology. 24 (2): 93–105. arXiv:1503.05285. doi:10.1089/cmb.2016.0190.
  • Andrews, G. E. (1998). The Theory of Partitions. Cambridge Mathematical Library (1st pbk ed.). Cambridge University Press. pp. 204–211. ISBN 0-521-63766-X.
  • Bell, E. T. (1927–1928). "Partition Polynomials". Annals of Mathematics. 29 (1/4): 38–46. doi:10.2307/1967979. JSTOR 1967979. MR 1502817.
  • Boyadzhiev, K. N. (2009). "Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals". Abstract and Applied Analysis. 2009: Article ID 168672. arXiv:0909.0979. Bibcode:2009AbApA2009....1B. doi:10.1155/2009/168672. (contains also elementary review of the concept Bell-polynomials)
  • Charalambides, C. A. (2002). Enumerative Combinatorics. Chapman & Hall / CRC. p. 632. ISBN 9781584882909.
  • Comtet, L. (1974). Advanced Combinatorics: The Art of Finite and Infinite Expansions. Dordrecht, Holland / Boston, U.S.: Reidel Publishing Company.
  • Griffiths, M. (2012). "Families of sequences from a class of multinomial sums". Journal of Integer Sequences. 15: Article 12.1.8. MR 2872465.
  • Kruchinin, V. V. (2011). "Derivation of Bell Polynomials of the Second Kind". arXiv:1104.5065.
  • Noschese, S.; Ricci, P. E. (2003). "Differentiation of Multivariable Composite Functions and Bell Polynomials". Journal of Computational Analysis and Applications. 5 (3): 333–340. doi:10.1023/A:1023227705558.
  • Roman, S. (2013). The Umbral Calculus. Dover Publications. p. 208. ISBN 9780486153421.
  • Voinov, V. G.; Nikulin, M. S. (1994). "On power series, Bell polynomials, Hardy–Ramanujan–Rademacher problem and its statistical applications". Kybernetika. 30 (3): 343–358. ISSN 0023-5954.
Adjugate matrix

In linear algebra, the adjugate, classical adjoint, or adjunct of a square matrix is the transpose of its cofactor matrix.The adjugate has sometimes been called the "adjoint", but today the "adjoint" of a matrix normally refers to its corresponding adjoint operator, which is its conjugate transpose.

Bell number

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan, but they are named after Eric Temple Bell, who wrote about them in the 1930s.

Starting with B0 = B1 = 1, the first few Bell numbers are:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ... (sequence A000110 in the OEIS).The nth of these numbers, Bn, counts the number of different ways to partition a set that has exactly n elements, or equivalently, the number of equivalence relations on it.

Outside of mathematics, the same number also counts the number of different rhyme schemes for n-line poems.As well as appearing in counting problems, these numbers have a different interpretation, as moments of probability distributions. In particular, Bn is the nth moment of a Poisson distribution with mean 1.

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

Many such sequences exist. The set of all such sequences forms a Lie group under the operation of umbral composition, explained below. Every sequence of binomial type may be expressed in terms of the Bell polynomials. Every sequence of binomial type is a Sheffer sequence (but most Sheffer sequences are not of binomial type). Polynomial sequences put on firm footing the vague 19th century notions of umbral calculus.

Cayley–Hamilton theorem

In linear algebra, the Cayley–Hamilton theorem (named after the mathematicians Arthur Cayley and William Rowan Hamilton) states that every square matrix over a commutative ring (such as the real or complex field) satisfies its own characteristic equation.

If A is a given n×n matrix and In  is the n×n identity matrix, then the characteristic polynomial of A is defined as

where det is the determinant operation and λ is a scalar element of the base ring. Since the entries of the matrix are (linear or constant) polynomials in λ, the determinant is also an n-th order monic polynomial in λ. The Cayley–Hamilton theorem states that substituting the matrix A for λ in this polynomial results in the zero matrix,

.

The powers of A, obtained by substitution from powers of λ, are defined by repeated matrix multiplication; the constant term of p(λ) gives a multiple of the power A0, which is defined as the identity matrix. The theorem allows An to be expressed as a linear combination of the lower matrix powers of A. When the ring is a field, the Cayley–Hamilton theorem is equivalent to the statement that the minimal polynomial of a square matrix divides its characteristic polynomial.

The theorem was first proved in 1853 in terms of inverses of linear functions of quaternions, a non-commutative ring, by Hamilton. This corresponds to the special case of certain 4 × 4 real or 2 × 2 complex matrices. The theorem holds for general quaternionic matrices. Cayley in 1858 stated it for 3 × 3 and smaller matrices, but only published a proof for the 2 × 2 case. The general case was first proved by Frobenius in 1878.

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 distributions whose moments are identical will have identical cumulants as well, and similarly the cumulants determine the moments.

The first cumulant is the mean, the second cumulant is the variance, and the third cumulant is the same as the third central moment. But fourth and higher-order cumulants are not equal to central moments. In some cases theoretical treatments of problems in terms of cumulants are simpler than those using moments. In particular, when two or more random variables are statistically independent, the nth-order cumulant of their sum is equal to the sum of their nth-order cumulants. As well, the third and higher-order cumulants of a normal distribution are zero, and it is the only distribution with this property.

Just as for moments, where joint moments are used for collections of random variables, it is possible to define joint cumulants.

Edgeworth series

The Gram–Charlier A series (named in honor of Jørgen Pedersen Gram and Carl Charlier), and the Edgeworth series (named in honor of Francis Ysidro Edgeworth) are series that approximate a probability distribution in terms of its cumulants. The series are the same; but, the arrangement of terms (and thus the accuracy of truncating the series) differ. The key idea of these expansions is to write the characteristic function of the distribution whose probability density function f is to be approximated in terms of the characteristic function of a distribution with known and suitable properties, and to recover f through the inverse Fourier transform.

Eric Temple Bell

Eric Temple Bell (February 7, 1883 – December 21, 1960) was a Scottish-born mathematician and science fiction writer who lived in the United States for most of his life. He published non-fiction using his given name and fiction as John Taine.

Faà di Bruno's formula

Faà di Bruno's formula is an identity in mathematics generalizing the chain rule to higher derivatives, named after Francesco Faà di Bruno (1855, 1857), though 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 stated the formula in a calculus textbook, considered the first published reference on the subject.

Perhaps the most well-known form of Faà di Bruno's formula says that

where the sum is over all n-tuples of nonnegative integers (m1, …, mn) satisfying the constraint

Sometimes, to give it a memorable pattern, it is written in a way in which the coefficients that have the combinatorial interpretation discussed below are less explicit:

Combining the terms with the same value of m1 + m2 + ... + mn = k and noticing that m j has to be zero for j > n − k + 1 leads to a somewhat simpler formula expressed in terms of Bell polynomials Bn,k(x1,...,xnk+1):

Fractional Poisson process

In probability theory, a fractional Poisson process is a stochastic process to model the long-memory dynamics of a stream of counts. The time interval between each pair of consecutive counts follows the non-exponential power-law distribution with parameter , which has physical dimension , where . In other words, fractional Poisson process is non-Markov counting stochastic process which exhibits non-exponential distribution of interarrival times. The fractional Poisson process is a continuous-time process which can be thought of as natural generalization of the well-known Poisson process. Fractional Poisson probability distribution is a new member of discrete probability distributions.

The fractional Poisson process, Fractional compound Poisson process and fractional Poisson probability distribution function have been invented, developed and encouraged for applications by Nick Laskin (2003) who coined the terms fractional Poisson process, Fractional compound Poisson process and fractional Poisson probability distribution function.

List of partition topics

Generally, a partition is a division of a whole into non-overlapping parts. Among the kinds of partitions considered in mathematics are

partition of a set or an ordered partition of a set,

partition of a graph,

partition of an integer,

partition of an interval,

partition of unity,

partition of a matrix; see block matrix, and

partition of the sum of squares in statistics problems, especially in the analysis of variance,

quotition and partition, two ways of viewing the operation of division of integers.

List of polynomial topics

This is a list of polynomial topics, by Wikipedia page. See also trigonometric polynomial, list of algebraic geometry topics.

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). Named symmetric functions, and other special polynomials, are included.

List of triangle topics

This list of triangle topics includes things related to the geometric shape, either abstractly, as in idealizations studied by geometers, or in triangular arrays such as Pascal's triangle or triangular matrices, or concretely in physical space. It does not include metaphors like "love triangle" in which the word has no reference to the geometric shape.

Michael Christopher Wendl

Michael Christopher Wendl is a mathematician and biomedical engineer who has worked on DNA sequencing theory, covering and matching problems in probability, theoretical fluid mechanics, and co-wrote Phred. He was a scientist on the Human Genome Project and has done bioinformatics and biostatistics work in cancer. Wendl is of ethnic German heritage and is the son of the aerospace engineer Michael J. Wendl.

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. Polynomial sequences are a topic of interest in enumerative combinatorics and algebraic combinatorics, as well as applied mathematics.

Touchard polynomials

The Touchard polynomials, studied by Jacques Touchard (1939), also called the exponential polynomials or Bell polynomials, comprise a polynomial sequence of binomial type defined by

where is a Stirling number of the second kind, i.e., the number of partitions of a set of size n into k disjoint non-empty subsets.

Triangular array

In mathematics and computing, a triangular array of numbers, polynomials, or the like, is a doubly indexed sequence in which each row is only as long as the row's own index.

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.