Polynomials in combinatorial mathematics
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.
Definitions
Exponential Bell polynomials
The partial or incomplete exponential Bell polynomials are a triangular array of polynomials given by
![{\displaystyle {\begin{aligned}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}}\\&=n!\sum \prod _{i=1}^{n-k+1}{\frac {x_{i}^{j_{i}}}{(i!)^{j_{i}}j_{i}!}},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f784b4ac5a41ed069c39cd252e7b5a6c7b7f37e)
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:
![{\displaystyle j_{1}+j_{2}+\cdots +j_{n-k+1}=k,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/376e645b6953b48eafbe7f32b7d7ad67c8a2a238)
![{\displaystyle j_{1}+2j_{2}+3j_{3}+\cdots +(n-k+1)j_{n-k+1}=n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a84e925f91d3aba7e34521fd214cc5e0e73b01b7)
The sum
![{\displaystyle {\begin{aligned}B_{n}(x_{1},\dots ,x_{n})&=\sum _{k=1}^{n}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})\\&=n!\sum _{1j_{1}+\ldots +nj_{n}=n}\prod _{i=1}^{n}{\frac {x_{i}^{j_{i}}}{(i!)^{j_{i}}j_{i}!}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/387d5c54feca1862742da64637edeaa210e37527)
is called the nth complete exponential Bell polynomial.
Ordinary Bell polynomials
Likewise, the partial ordinary Bell polynomial is defined by
![{\displaystyle {\hat {B}}_{n,k}(x_{1},x_{2},\ldots ,x_{n-k+1})=\sum {\frac {k!}{j_{1}!j_{2}!\cdots j_{n-k+1}!}}x_{1}^{j_{1}}x_{2}^{j_{2}}\cdots x_{n-k+1}^{j_{n-k+1}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf9768a96080b24379081ddad0f059e009125c42)
where the sum runs over all sequences j1, j2, j3, ..., jn−k+1 of non-negative integers such that
![{\displaystyle j_{1}+j_{2}+\cdots +j_{n-k+1}=k,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/376e645b6953b48eafbe7f32b7d7ad67c8a2a238)
![{\displaystyle j_{1}+2j_{2}+\cdots +(n-k+1)j_{n-k+1}=n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41023eeadb5b9721627a217c02f94cf2030db2dd)
Thanks to the first condition on indices, we can rewrite the formula as
![{\displaystyle {\hat {B}}_{n,k}(x_{1},x_{2},\ldots ,x_{n-k+1})=\sum {\binom {k}{j_{1},j_{2},\ldots ,j_{n-k+1}}}x_{1}^{j_{1}}x_{2}^{j_{2}}\cdots x_{n-k+1}^{j_{n-k+1}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/697e92d98ed8eb525414aa9d7f9ec63b6947bed6)
where we have used the multinomial coefficient.
The ordinary Bell polynomials can be expressed in the terms of exponential Bell polynomials:
![{\displaystyle {\hat {B}}_{n,k}(x_{1},x_{2},\ldots ,x_{n-k+1})={\frac {k!}{n!}}B_{n,k}(1!\cdot x_{1},2!\cdot x_{2},\ldots ,(n-k+1)!\cdot x_{n-k+1}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58e51fbdd9c1a11ce2dd41f36af8377ecf5c0249)
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
![{\displaystyle B_{3,2}(x_{1},x_{2})=3x_{1}x_{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6280104864fb85715300296387cf3a26597624a)
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
![{\displaystyle B_{6,2}(x_{1},x_{2},x_{3},x_{4},x_{5})=6x_{5}x_{1}+15x_{4}x_{2}+10x_{3}^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f14c4a8c1824a1d39ef2cdda152cb767aa5e9b0)
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
![{\displaystyle B_{6,2}(x_{1},x_{2},x_{3},x_{4},x_{5})=6x_{5}x_{1}+15x_{4}x_{2}+10x_{3}^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f652d968d23f71f42f7c36dc986b334533e60e73)
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,
![{\displaystyle B_{6,3}(x_{1},x_{2},x_{3},x_{4})=15x_{4}x_{1}^{2}+60x_{3}x_{2}x_{1}+15x_{2}^{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/201279c5db782fa9fe3ca5e10ef39fff66f20c61)
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
:
Properties
Generating function
The exponential partial Bell polynomials can be defined by the double series expansion of its generating function:
![{\displaystyle {\begin{aligned}\Phi (t,u)&=\exp \left(u\sum _{j=1}^{\infty }x_{j}{\frac {t^{j}}{j!}}\right)=\sum _{n\geq k\geq 0}B_{n,k}(x_{1},\ldots ,x_{n-k+1}){\frac {t^{n}}{n!}}u^{k}\\&=1+\sum _{n=1}^{\infty }{\frac {t^{n}}{n!}}\sum _{k=1}^{n}u^{k}B_{n,k}(x_{1},\ldots ,x_{n-k+1}).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/614ae2d265c5daeb121ea25ce906ec12f73c0adb)
In other words, by what amounts to the same, by the series expansion of the k-th power:
![{\displaystyle {\frac {1}{k!}}\left(\sum _{j=1}^{\infty }x_{j}{\frac {t^{j}}{j!}}\right)^{k}=\sum _{n=k}^{\infty }B_{n,k}(x_{1},\ldots ,x_{n-k+1}){\frac {t^{n}}{n!}},\qquad k=0,1,2,\ldots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/02970423694058e3e0eaa407de58d25cf69c1438)
The complete exponential Bell polynomial is defined by
, or in other words:
![{\displaystyle \Phi (t,1)=\exp \left(\sum _{j=1}^{\infty }x_{j}{\frac {t^{j}}{j!}}\right)=\sum _{n=0}^{\infty }B_{n}(x_{1},\ldots ,x_{n}){\frac {t^{n}}{n!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ce768817d826496a8dc5867122c5034c9652acc)
Thus, the n-th complete Bell polynomial is given by
![{\displaystyle B_{n}(x_{1},\ldots ,x_{n})=\left.\left({\frac {\partial }{\partial t}}\right)^{n}\exp \left(\sum _{j=1}^{n}x_{j}{\frac {t^{j}}{j!}}\right)\right|_{t=0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f877b9120900ce017be3ce3298216c9202c327cf)
Likewise, the ordinary partial Bell polynomial can be defined by the generating function
![{\displaystyle {\hat {\Phi }}(t,u)=\exp \left(u\sum _{j=1}^{\infty }x_{j}t^{j}\right)=\sum _{n\geq k\geq 0}{\hat {B}}_{n,k}(x_{1},\ldots ,x_{n-k+1})t^{n}{\frac {u^{k}}{k!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d992033f62d975b9cbabfc60e310693e442705e)
Or, equivalently, by series expansion of the k-th power:
![{\displaystyle \left(\sum _{j=1}^{\infty }x_{j}t^{j}\right)^{k}=\sum _{n=k}^{\infty }{\hat {B}}_{n,k}(x_{1},\ldots ,x_{n-k+1})t^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee521d1d632d4ae5b60c0787a94b01b5464b5408)
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
![{\displaystyle B_{n+1}(x_{1},\ldots ,x_{n+1})=\sum _{i=0}^{n}{n \choose i}B_{n-i}(x_{1},\ldots ,x_{n-i})x_{i+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac7c4a7a474646c423fe9f682788a6de848e81e1)
with the initial value
.
The partial Bell polynomials can also be computed efficiently by a recurrence relation:
![{\displaystyle B_{n+1,k+1}(x_{1},\ldots ,x_{n-k+1})=\sum _{i=0}^{n-k}{\binom {n}{i}}x_{i+1}B_{n-i,k}(x_{1},\ldots ,x_{n-k-i+1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbc89f44f4addae8f33c62bc046057ee253f3137)
where
![{\displaystyle B_{0,0}=1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce2991221d8bfec82902425194feeea3a0ec442f)
![{\displaystyle B_{n,0}=0{\text{ for }}n\geq 1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc60e9853442c2290989a441b1c3abfece7d842b)
![{\displaystyle B_{0,k}=0{\text{ for }}k\geq 1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd6c6cc5d36eeb188f2d4b2c371211ed161eb3f1)
In addition:
![{\displaystyle B_{n,k_{1}+k_{2}}(x_{1},\ldots ,x_{n-k_{1}-k_{2}+1})={\frac {k_{1}!\,k_{2}!}{(k_{1}+k_{2})!}}\sum _{i=0}^{n}{\binom {n}{i}}B_{i,k_{1}}(x_{1},\ldots ,x_{i-k_{1}+1})B_{n-i,k_{2}}(x_{1},\ldots ,x_{n-i-k_{2}+1}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea73ef154ba6dd8f9c63e06c442405b6d6762056)
When
,
![{\displaystyle B_{n,n-a}(x_{1},\ldots ,x_{a+1})=\sum _{j=a+1}^{2a}{\frac {j!}{a!}}{\binom {n}{j}}x_{1}^{n-j}B_{a,j-a}{\Bigl (}{\frac {x_{2}}{2}},{\frac {x_{3}}{3}},\ldots ,{\frac {x_{2(a+1)-j}}{2(a+1)-j}}{\Bigr )}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f666db566f2feed2252e8902ece3d2f9061e85fd)
The complete Bell polynomials also satisfy the following recurrence differential formula:
![{\displaystyle {\begin{aligned}B_{n}(x_{1},\ldots ,x_{n})={\frac {1}{n-1}}\left[\sum _{i=2}^{n}\right.&\sum _{j=1}^{i-1}(i-1){\binom {i-2}{j-1}}x_{j}x_{i-j}{\frac {\partial B_{n-1}(x_{1},\dots ,x_{n-1})}{\partial x_{i-1}}}\\[5pt]&\left.{}+\sum _{i=2}^{n}\sum _{j=1}^{i-1}{\frac {x_{i+1}}{\binom {i}{j}}}{\frac {\partial ^{2}B_{n-1}(x_{1},\dots ,x_{n-1})}{\partial x_{j}\partial x_{i-j}}}\right.\\[5pt]&\left.{}+\sum _{i=2}^{n}x_{i}{\frac {\partial B_{n-1}(x_{1},\dots ,x_{n-1})}{\partial x_{i-1}}}\right].\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f8063f0be30dd504b0ae58533a3ce24749fcc34)
Derivatives
The partial derivatives of the complete Bell polynomials are given by
![{\displaystyle {\frac {\partial B_{n}}{\partial x_{i}}}(x_{1},\ldots ,x_{n})={\binom {n}{i}}B_{n-i}(x_{1},\ldots ,x_{n-i}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dec4502b946d6fa5bef33d09048e0d6a0dc5865)
Similarly, the partial derivatives of the partial Bell polynomials are given by
![{\displaystyle {\frac {\partial B_{n,k}}{\partial x_{i}}}(x_{1},\ldots ,x_{n-k+1})={\binom {n}{i}}B_{n-i,k-1}(x_{1},\ldots ,x_{n-i-k+2}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7611ef3c246acf407ecc576f8c173be6ba2ace8c)
If the arguments of the Bell polynomials are one-dimensional functions, the chain rule can be used to obtain
![{\displaystyle {\frac {d}{dx}}\left(B_{n,k}(a_{1}(x),\cdots ,a_{n-k+1}(x))\right)=\sum _{i=1}^{n-k+1}{\binom {n}{i}}a_{i}'(x)B_{n-i,k-1}(a_{1}(x),\cdots ,a_{n-i-k+2}(x)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ce23cf64bb1a655aea9757d90d9b935471cd07a)
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:
![{\displaystyle B_{n,k}(0!,1!,\dots ,(n-k)!)=c(n,k)=|s(n,k)|=\left[{n \atop k}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80296b6db513e5a685baf814971bb0b99c0fd4d5)
The sum of these values gives the value of the complete Bell polynomial on the sequence of factorials:
![{\displaystyle B_{n}(0!,1!,\dots ,(n-1)!)=\sum _{k=1}^{n}B_{n,k}(0!,1!,\dots ,(n-k)!)=\sum _{k=1}^{n}\left[{n \atop k}\right]=n!.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f302915466059274b3e9629a9b4b5831a14c037)
The value of the Bell polynomial Bn,k(x1,x2,...) on the sequence of ones equals a Stirling number of the second kind:
![{\displaystyle B_{n,k}(1,1,\dots ,1)=S(n,k)=\left\{{n \atop k}\right\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/925e9e4d5b0c074a48594f7ffbf86ed9a42b2933)
The sum of these values gives the value of the complete Bell polynomial on the sequence of ones:
![{\displaystyle B_{n}(1,1,\dots ,1)=\sum _{k=1}^{n}B_{n,k}(1,1,\dots ,1)=\sum _{k=1}^{n}\left\{{n \atop k}\right\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3465e93bd3166a24a0dbdc3f65999a1e6d1d932e)
which is the nth Bell number.
![{\displaystyle B_{n,k}(1!,2!,\ldots ,(n-k+1)!)={\binom {n-1}{k-1}}{\frac {n!}{k!}}=L(n,k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/542a6c10003b8520a828bc6a819f1fbd17b5d45e)
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:
![{\displaystyle T_{n}(x)=B_{n}(x,x,\dots ,x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51f270d47c85fe88df385af1b679edecb196cad3)
Inverse relations
If we define
![{\displaystyle y_{n}=\sum _{k=1}^{n}B_{n,k}(x_{1},\ldots ,x_{n-k+1}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1997d8b74122aa344bd1f16a30856c34cda7e581)
then we have the inverse relationship
![{\displaystyle x_{n}=\sum _{k=1}^{n}(-1)^{k-1}(k-1)!B_{n,k}(y_{1},\ldots ,y_{n-k+1}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f84dbdda18620a84a50301e3ff6d21bc6a574c36)
More generally,[5][6] given some function
admitting an inverse
,
![{\displaystyle y_{n}=\sum _{k=0}^{n}f^{(k)}(a)\,B_{n,k}(x_{1},\ldots ,x_{n-k+1})\quad \Leftrightarrow \quad x_{n}=\sum _{k=0}^{n}g^{(k)}{\big (}f(a){\big )}\,B_{n,k}(y_{1},\ldots ,y_{n-k+1}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92b04a73d156462fdae58be27f89a991290442b0)
The complete Bell polynomial can be expressed as determinants:
![{\displaystyle 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}&\cdots &\cdots &x_{n}\\\\-1&x_{1}&{n-2 \choose 1}x_{2}&{n-2 \choose 2}x_{3}&\cdots &\cdots &x_{n-1}\\\\0&-1&x_{1}&{n-3 \choose 1}x_{2}&\cdots &\cdots &x_{n-2}\\\\0&0&-1&x_{1}&\cdots &\cdots &x_{n-3}\\\\0&0&0&-1&\cdots &\cdots &x_{n-4}\\\\\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\\\0&0&0&0&\cdots &-1&x_{1}\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c419a7cdba9f6bab579e6a885650c878037429c)
and
![{\displaystyle B_{n}(x_{1},\dots ,x_{n})=\det {\begin{bmatrix}{\frac {x_{1}}{0!}}&{\frac {x_{2}}{1!}}&{\frac {x_{3}}{2!}}&{\frac {x_{4}}{3!}}&\cdots &\cdots &{\frac {x_{n}}{(n-1)!}}\\\\-1&{\frac {x_{1}}{0!}}&{\frac {x_{2}}{1!}}&{\frac {x_{3}}{2!}}&\cdots &\cdots &{\frac {x_{n-1}}{(n-2)!}}\\\\0&-2&{\frac {x_{1}}{0!}}&{\frac {x_{2}}{1!}}&\cdots &\cdots &{\frac {x_{n-2}}{(n-3)!}}\\\\0&0&-3&{\frac {x_{1}}{0!}}&\cdots &\cdots &{\frac {x_{n-3}}{(n-4)!}}\\\\0&0&0&-4&\cdots &\cdots &{\frac {x_{n-4}}{(n-5)!}}\\\\\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\\\0&0&0&0&\cdots &-(n-1)&{\frac {x_{1}}{0!}}\end{bmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0713fc90933eb2e7b4fa31b800ce8d71b0933363)
Convolution identity
For sequences xn, yn, n = 1, 2, ..., define a convolution by:
![{\displaystyle (x{\mathbin {\diamondsuit }}y)_{n}=\sum _{j=1}^{n-1}{n \choose j}x_{j}y_{n-j}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da2ef3912cbb8966f32b4bd91a527938214949fb)
The bounds of summation are 1 and n − 1, not 0 and n .
Let
be the nth term of the sequence
![{\displaystyle \displaystyle \underbrace {x{\mathbin {\diamondsuit }}\cdots {\mathbin {\diamondsuit }}x} _{k{\text{ factors}}}.\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c53c734475494a47013090621c682ceec28139e)
Then
![{\displaystyle B_{n,k}(x_{1},\dots ,x_{n-k+1})={x_{n}^{k\diamondsuit } \over k!}.\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c24df09124d4a1da98e42742190ac82d9e44187b)
For example, let us compute
. We have
![{\displaystyle x=(x_{1}\ ,\ x_{2}\ ,\ x_{3}\ ,\ x_{4}\ ,\dots )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7835992b71cb6146d765266b1a535dab038cd59)
![{\displaystyle x{\mathbin {\diamondsuit }}x=(0,\ 2x_{1}^{2}\ ,\ 6x_{1}x_{2}\ ,\ 8x_{1}x_{3}+6x_{2}^{2}\ ,\dots )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62be2968cd28a22822ef8f04012c34a36268f52f)
![{\displaystyle x{\mathbin {\diamondsuit }}x{\mathbin {\diamondsuit }}x=(0\ ,\ 0\ ,\ 6x_{1}^{3}\ ,\ 36x_{1}^{2}x_{2}\ ,\dots )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fafb740984d661847d74d6052dd1d72bb57521c)
and thus,
![{\displaystyle B_{4,3}(x_{1},x_{2})={\frac {(x{\mathbin {\diamondsuit }}x{\mathbin {\diamondsuit }}x)_{4}}{3!}}=6x_{1}^{2}x_{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/800fc438c908e9bcb4efde974f051e87eb679fed)
Other identities
which gives the idempotent number.
. - The complete Bell polynomials satisfy the binomial type relation:
![{\displaystyle B_{n}(x_{1}+y_{1},\ldots ,x_{n}+y_{n})=\sum _{i=0}^{n}{n \choose i}B_{n-i}(x_{1},\ldots ,x_{n-i})B_{i}(y_{1},\ldots ,y_{i}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9e6ae23cc48bb808be2c11c7e076bbc9d1c7912)
![{\displaystyle B_{n,k}{\Bigl (}{\frac {x_{q+1}}{\binom {q+1}{q}}},{\frac {x_{q+2}}{\binom {q+2}{q}}},\ldots {\Bigr )}={\frac {n!(q!)^{k}}{(n+qk)!}}B_{n+qk,k}(\ldots ,0,0,x_{q+1},x_{q+2},\ldots ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1a178b93211c4e075b1c135ae14d3bd17aeb36d)
- This corrects the omission of the factor
in Comtet's book.
- Special cases of partial Bell polynomials:
![{\displaystyle {\begin{aligned}B_{n,1}(x_{1},\ldots ,x_{n})={}&x_{n}\\B_{n,2}(x_{1},\ldots ,x_{n-1})={}&{\frac {1}{2}}\sum _{k=1}^{n-1}{\binom {n}{k}}x_{k}x_{n-k}\\B_{n,n}(x_{1})={}&x_{1}^{n}\\B_{n,n-1}(x_{1},x_{2})={}&{\binom {n}{2}}x_{1}^{n-2}x_{2}\\B_{n,n-2}(x_{1},x_{2},x_{3})={}&{\binom {n}{3}}x_{1}^{n-3}x_{3}+3{\binom {n}{4}}x_{1}^{n-4}x_{2}^{2}\\B_{n,n-3}(x_{1},x_{2},x_{3},x_{4})={}&{\binom {n}{4}}x_{1}^{n-4}x_{4}+10{\binom {n}{5}}x_{1}^{n-5}x_{2}x_{3}+15{\binom {n}{6}}x_{1}^{n-6}x_{2}^{3}\\B_{n,n-4}(x_{1},x_{2},x_{3},x_{4},x_{5})={}&{\binom {n}{5}}x_{1}^{n-5}x_{5}+5{\binom {n}{6}}x_{1}^{n-6}(3x_{2}x_{4}+2x_{3}^{2})+105{\binom {n}{7}}x_{1}^{n-7}x_{2}^{2}x_{3}\\&+105{\binom {n}{8}}x_{1}^{n-8}x_{2}^{4}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f78a28cdddd0ee6071c41407da10cc81f2226e8)
Examples
The first few complete Bell polynomials are:
![{\displaystyle {\begin{aligned}B_{0}={}&1,\\[8pt]B_{1}(x_{1})={}&x_{1},\\[8pt]B_{2}(x_{1},x_{2})={}&x_{1}^{2}+x_{2},\\[8pt]B_{3}(x_{1},x_{2},x_{3})={}&x_{1}^{3}+3x_{1}x_{2}+x_{3},\\[8pt]B_{4}(x_{1},x_{2},x_{3},x_{4})={}&x_{1}^{4}+6x_{1}^{2}x_{2}+4x_{1}x_{3}+3x_{2}^{2}+x_{4},\\[8pt]B_{5}(x_{1},x_{2},x_{3},x_{4},x_{5})={}&x_{1}^{5}+10x_{2}x_{1}^{3}+15x_{2}^{2}x_{1}+10x_{3}x_{1}^{2}+10x_{3}x_{2}+5x_{4}x_{1}+x_{5}\\[8pt]B_{6}(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})={}&x_{1}^{6}+15x_{2}x_{1}^{4}+20x_{3}x_{1}^{3}+45x_{2}^{2}x_{1}^{2}+15x_{2}^{3}+60x_{3}x_{2}x_{1}\\&{}+15x_{4}x_{1}^{2}+10x_{3}^{2}+15x_{4}x_{2}+6x_{5}x_{1}+x_{6},\\[8pt]B_{7}(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7})={}&x_{1}^{7}+21x_{1}^{5}x_{2}+35x_{1}^{4}x_{3}+105x_{1}^{3}x_{2}^{2}+35x_{1}^{3}x_{4}\\&{}+210x_{1}^{2}x_{2}x_{3}+105x_{1}x_{2}^{3}+21x_{1}^{2}x_{5}+105x_{1}x_{2}x_{4}\\&{}+70x_{1}x_{3}^{2}+105x_{2}^{2}x_{3}+7x_{1}x_{6}+21x_{2}x_{5}+35x_{3}x_{4}+x_{7}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9601065e082a0079a81671a8361d2d6d0332b2cc)
Applications
Faà di Bruno's formula may be stated in terms of Bell polynomials as follows:
![{\displaystyle {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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea83c08f3a6a28b816eca476ed8318a3d27e6627)
Similarly, a power-series version of Faà di Bruno's formula may be stated using Bell polynomials as follows. Suppose
![{\displaystyle f(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\qquad {\text{and}}\qquad g(x)=\sum _{n=0}^{\infty }{b_{n} \over n!}x^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ad2400db7bef0a8af96c19e32dd980687d1bbd3)
Then
![{\displaystyle g(f(x))=\sum _{n=1}^{\infty }{\frac {\sum _{k=0}^{n}b_{k}B_{n,k}(a_{1},\dots ,a_{n-k+1})}{n!}}x^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/754eded5ae61e323b474683a0ee0468bb54ea72a)
In particular, the complete Bell polynomials appear in the exponential of a formal power series:
![{\displaystyle \exp \left(\sum _{i=1}^{\infty }{a_{i} \over i!}x^{i}\right)=\sum _{n=0}^{\infty }{B_{n}(a_{1},\dots ,a_{n}) \over n!}x^{n},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7a868dbfcf24bb88de489a9a65d91dcd203b8ae)
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
![{\displaystyle f(w)=\sum _{k=0}^{\infty }f_{k}{\frac {w^{k}}{k!}},\qquad {\text{and}}\qquad g(z)=\sum _{k=0}^{\infty }g_{k}{\frac {z^{k}}{k!}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f473f60c61f13baba7164392b7d7491d10d7058)
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
![{\displaystyle g_{n}={\frac {1}{f_{1}^{n}}}\sum _{k=1}^{n-1}(-1)^{k}n^{\bar {k}}B_{n-1,k}({\hat {f}}_{1},{\hat {f}}_{2},\ldots ,{\hat {f}}_{n-k}),\qquad n\geq 2,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f421c6039c1fe32b3a6f6f0231bb101a23a34af)
with
and
is the rising factorial, and
Asymptotic expansion of Laplace-type integrals
Consider the integral of the form
![{\displaystyle I(\lambda )=\int _{a}^{b}e^{-\lambda f(x)}g(x)\,\mathrm {d} x,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f365582c93452cd7afec6727c58a2872bfdb029)
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+,
![{\displaystyle f(x)\sim f(a)+\sum _{k=0}^{\infty }a_{k}(x-a)^{k+\alpha },}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6714770c1135cc5a116cea6e8a4b90fa8f91f2b9)
![{\displaystyle g(x)\sim \sum _{k=0}^{\infty }b_{k}(x-a)^{k+\beta -1},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a42981a5307f8ea0402aafc669251bc7616e13a)
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
![{\displaystyle I(\lambda )\sim e^{-\lambda f(a)}\sum _{n=0}^{\infty }\Gamma {\Big (}{\frac {n+\beta }{\alpha }}{\Big )}{\frac {c_{n}}{\lambda ^{(n+\beta )/\alpha }}}\qquad {\text{as}}\quad \lambda \rightarrow \infty ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/924d366151626748f942f9df7e606285d3c6aa93)
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:
![{\displaystyle c_{n}={\frac {1}{\alpha a_{0}^{(n+\beta )/\alpha }}}\sum _{k=0}^{n}b_{n-k}\sum _{j=0}^{k}{\binom {-{\frac {n+\beta }{\alpha }}}{j}}{\frac {1}{a_{0}^{j}}}{\hat {B}}_{k,j}(a_{1},a_{2},\ldots ,a_{k-j+1}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d332d4dd87e86c276d33841aabca7e276e7dd5e2)
Symmetric polynomials
The elementary symmetric polynomial
and the power sum symmetric polynomial
can be related to each other using Bell polynomials as:
![{\displaystyle {\begin{aligned}e_{n}&={\frac {1}{n!}}\;B_{n}(p_{1},-1!p_{2},2!p_{3},-3!p_{4},\ldots ,(-1)^{n-1}(n-1)!p_{n})\\&={\frac {(-1)^{n}}{n!}}\;B_{n}(-p_{1},-1!p_{2},-2!p_{3},-3!p_{4},\ldots ,-(n-1)!p_{n}),\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da5f05eaab1f84b4c4734e8192dcf1d0ef7a7428)
![{\displaystyle {\begin{aligned}p_{n}&={\frac {(-1)^{n-1}}{(n-1)!}}\sum _{k=1}^{n}(-1)^{k-1}(k-1)!\;B_{n,k}(e_{1},2!e_{2},3!e_{3},\ldots ,(n-k+1)!e_{n-k+1})\\&=(-1)^{n}\;n\;\sum _{k=1}^{n}{\frac {1}{k}}\;{\hat {B}}_{n,k}(-e_{1},\dots ,-e_{n-k+1}).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/712748cf8dc8d554f9c83086053f618c07d23605)
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:
![{\displaystyle \det(A)={\frac {(-1)^{n}}{n!}}B_{n}(s_{1},s_{2},\ldots ,s_{n}),~\qquad {\text{where }}s_{k}=-(k-1)!\operatorname {tr} (A^{k}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8866bdea66a67ebdec6120fe465d349cc864474f)
Cycle index of symmetric groups
The cycle index of the symmetric group
can be expressed in terms of complete Bell polynomials as follows:
![{\displaystyle Z(S_{n})={\frac {B_{n}(0!\,a_{1},1!\,a_{2},\dots ,(n-1)!\,a_{n})}{n!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2513576a6221070a3933c718cb1c1b45300eb7d8)
Moments and cumulants
The sum
![{\displaystyle \mu _{n}'=B_{n}(\kappa _{1},\dots ,\kappa _{n})=\sum _{k=1}^{n}B_{n,k}(\kappa _{1},\dots ,\kappa _{n-k+1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/811047805fe8d14b79fdd43b82fb0f22ee3c7b40)
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
![{\displaystyle \kappa _{n}=\sum _{k=1}^{n}(-1)^{k-1}(k-1)!B_{n,k}(\mu '_{1},\ldots ,\mu '_{n-k+1}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b8fed2eba1ba66575f7e9b9ea2148c047f680c8)
Hermite polynomials
Hermite polynomials can be expressed in terms of Bell polynomials as
![{\displaystyle \operatorname {He} _{n}(x)=B_{n}(x,-1,0,\ldots ,0),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea5a64ae157c0c5bf53a5076fe03f57866d807bc)
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
![{\displaystyle \exp \left(xt-{\frac {t^{2}}{2}}\right)=\sum _{n=0}^{\infty }\operatorname {He} _{n}(x){\frac {t^{n}}{n!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d25ae83ddf0b84c08b5a03ab43ec28ec6abf673)
with that of Bell polynomials.
Representation of polynomial sequences of binomial type
For any sequence a1, a2, …, an of scalars, let
![{\displaystyle p_{n}(x)=B_{n}(a_{1}x,\ldots ,a_{n}x)=\sum _{k=1}^{n}B_{n,k}(a_{1},\dots ,a_{n-k+1})x^{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c13de893c5d46ff5c4ea6be264c05ec28f8524b8)
Then this polynomial sequence is of binomial type, i.e. it satisfies the binomial identity
![{\displaystyle p_{n}(x+y)=\sum _{k=0}^{n}{n \choose k}p_{k}(x)p_{n-k}(y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/591f6d85d48995973380a7ecda596712db59452d)
- 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
![{\displaystyle h(x)=\sum _{k=1}^{\infty }{a_{k} \over k!}x^{k},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a853eacf30e7733bf33f49a75d118c93eee7fc95)
then for all n,
![{\displaystyle h^{-1}\left({d \over dx}\right)p_{n}(x)=np_{n-1}(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa74030f571f23d9a8bc9eb52319c4d934cc29d3)
Software
Bell polynomials are implemented in:
See also
Notes
- ^ 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.
- ^ 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.
References
- Abbas, M.; Bouroubi, S. (2005). "On new identities for Bell's polynomial". Discrete Math. 293 (1–3): 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. PMID 28045556. S2CID 9678733.
- 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.
- Bell, E. T. (1934). "Exponential Polynomials". Annals of Mathematics. 35 (2): 258–277. doi:10.2307/1968431. JSTOR 1968431. MR 1503161.
- Boyadzhiev, K. N. (2009). "Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals". Abstract and Applied Analysis. 2009: 1–18. arXiv:0909.0979. Bibcode:2009AbApA2009....1B. doi:10.1155/2009/168672. S2CID 1608664. (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. Archived from the original on 2017-06-01. Retrieved 2019-07-02.
- Cvijović, D. (2011). "New identities for the partial Bell polynomials" (PDF). Applied Mathematics Letters. 24 (9): 1544–1547. doi:10.1016/j.aml.2011.03.043. S2CID 45311678. Archived (PDF) from the original on 2020-03-09. Retrieved 2020-06-05.
- Griffiths, M. (2012). "Families of sequences from a class of multinomial sums". Journal of Integer Sequences. 15: Article 12.1.8. MR 2872465. Archived from the original on 2014-05-02. Retrieved 2012-06-27.
- Kruchinin, V. V. (2011). "Derivation of Bell Polynomials of the Second Kind". arXiv:1104.5065 [math.CO].
- 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. S2CID 118361207.
- 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.