Editing Bell polynomials

{{Short description|Polynomials in combinatorial mathematics}}
{{for|a different family of polynomials B<sub>n</sub>''(''x'')'' occasionally called Bell polynomials|Touchard polynomials}}

In [[combinatorics|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 numbers|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

:<math>\begin{align}
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{align}</math>

where the sum is taken over all sequences ''j''<sub>1</sub>, ''j''<sub>2</sub>, ''j''<sub>3</sub>, ..., ''j''<sub>''n''−''k''+1</sub> of non-negative integers such that these two conditions are satisfied:

:<math>j_1 + j_2 + \cdots + j_{n-k+1} = k, </math> 
:<math>j_1 + 2 j_2 + 3 j_3 + \cdots + (n-k+1)j_{n-k+1} = n.</math>

The sum

:<math>\begin{align}
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{align}</math>

is called the ''n''th ''complete exponential Bell polynomial''.

===Ordinary Bell polynomials===
Likewise, the partial ''ordinary'' Bell polynomial is defined by
:<math>\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}}, </math>
where the sum runs over all sequences ''j''<sub>1</sub>, ''j''<sub>2</sub>, ''j''<sub>3</sub>, ..., ''j''<sub>''n''−''k''+1</sub> of non-negative integers such that
:<math>j_1 + j_2 + \cdots + j_{n-k+1} = k,</math>
:<math>j_1 + 2 j_2 + \cdots + (n-k+1)j_{n-k+1} = n.</math>

Thanks to the first condition on indices, we can rewrite the formula as
:<math>\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}}, </math>

where we have used the [[Multinomial theorem|multinomial coefficient]].

The ordinary Bell polynomials can be expressed in the terms of exponential Bell polynomials:
:<math>\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}).</math>

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

:<math>B_{3,2}(x_1,x_2) = 3 x_1 x_2. </math>

Here, the subscripts of ''B''<sub>3,2</sub> tell us that we are considering the partitioning of a set with 3 elements into 2 blocks. The subscript of each ''x''<sub>i</sub> indicates the presence of a block with ''i'' elements (or block of size ''i'') in a given partition. So here, ''x''<sub>2</sub> indicates the presence of a block with two elements. Similarly, ''x''<sub>1</sub> indicates the presence of a block with a single element. The exponent of ''x''<sub>i</sub><sup>j</sup> indicates that there are ''j'' such blocks of size ''i'' in a single partition. Here, the fact that both ''x''<sub>1</sub> and ''x''<sub>2</sub> 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 ''B''<sub>''n'',1</sub> = ''x''<sub>''n''</sub>. Similarly, since there is only one way that a set with ''n'' elements be divided into ''n'' singletons, ''B''<sub>''n'',''n''</sub> = ''x''<sub>1</sub><sup>''n''</sup>.

As a more complicated example, consider

:<math>B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_2+10x_3^2.</math>

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 ''B''<sub>3,2</sub>. 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''<sub>6,2</sub>.  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 ''B<sub>n</sub>'' is thus equal to the total number of integer partitions of&nbsp;''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''<sub>1</sub> + ''j''<sub>2</sub> + ... = ''k'' . Thus, given a complete Bell polynomial ''B<sub>n</sub>'', we can separate the partial Bell polynomial ''B<sub>n,k</sub>'' by collecting all those monomials with degree ''k''.

Finally, if we disregard the sizes of the blocks and put all ''x''<sub>''i''</sub> = ''x'', then the summation of the coefficients of the partial Bell polynomial ''B''<sub>''n'',''k''</sub> 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 ''B<sub>n</sub>'' 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 [[integer partition|partitioned]] into a sum in which "1" appears ''j''<sub>1</sub> times, "2" appears ''j''<sub>2</sub> times, and so on, then the number of [[partition of a set|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

:<math>B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_2+10x_3^2</math>

because the ways to partition a set of 6 elements as 2 blocks are

:6 ways to partition a set of 6 as 5&nbsp;+&nbsp;1,
:15 ways to partition a set of 6 as 4&nbsp;+&nbsp;2, and
:10 ways to partition a set of 6 as 3&nbsp;+&nbsp;3.

Similarly,

:<math>B_{6,3}(x_1,x_2,x_3,x_4)=15x_4x_1^2+60x_3x_2x_1+15x_2^3</math>

because the ways to partition a set of 6 elements as 3 blocks are

:15 ways to partition a set of 6 as 4&nbsp;+&nbsp;1&nbsp;+&nbsp;1,
:60 ways to partition a set of 6 as 3&nbsp;+&nbsp;2&nbsp;+&nbsp;1, and
:15 ways to partition a set of 6 as 2&nbsp;+&nbsp;2&nbsp;+&nbsp;2.

==Table of values==

Below is a [[triangular array]] of the incomplete Bell polynomials <math>B_{n,k}(x_1,x_2,\dots,x_{n-k+1})</math>:
{| style="text-align:right;" class="wikitable"
|-
! {{diagonal split header|''n''|''k''}}
! {{rh|align=right}} | 0
! {{rh|align=right}} | 1
! {{rh|align=right}} | 2
! {{rh|align=right}} | 3
! {{rh|align=right}} | 4
! {{rh|align=right}} | 5
! {{rh|align=right}} | 6
|-
! {{rh|align=right}} | 0
| <math>1</math>
|-
! {{rh|align=right}} | 1
| <math>0</math>
| <math>x_1</math>
|-
! {{rh|align=right}} | 2
| <math>0</math>
| <math>x_2</math>
| <math>x_1^2</math>
|-
! {{rh|align=right}} | 3
| <math>0</math>
| <math>x_3</math>
| <math>3x_1x_2</math>
| <math>x_1^3</math>
|-
! {{rh|align=right}} | 4
| <math>0</math>
| <math>x_4</math>
| <math>3x_2^2+4x_1x_3</math>
| <math>6x_1^2x_2</math>
| <math>x_1^4</math>
|-
! {{rh|align=right}} | 5
| <math>0</math>
| <math>x_5</math>
| <math>10x_2x_3+5x_1x_4</math>
| <math>15x_1x_2^2+10x_1^2x_3</math>
| <math>10x_1^3x_2</math>
| <math>x_1^5</math>
|-
! {{rh|align=right}} | 6
| <math>0</math>
| <math>x_6</math>
| <math>10x_3^2+15x_2x_4+6x_1x_5</math>
| <math>15x_2^3+60x_1x_2x_3+15x_1^2x_4</math>
| <math>45x_1^2x_2^2+20x_1^3x_3</math>
| <math>15x_1^4x_2</math>
| <math>x_1^6</math>
|}

==Properties==

===Generating function===
The exponential partial Bell polynomials can be defined by the double series expansion of its generating function:
:<math> 
\begin{align}
\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{align}
</math>

In other words, by what amounts to the same, by the series expansion of the ''k''-th power:
:<math> \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  </math>
 
The complete exponential Bell polynomial is defined by <math>\Phi(t,1)</math>, or in other words:
:<math> \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!}.</math>

Thus, the ''n''-th complete Bell polynomial is given by
:<math> 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}. </math>

Likewise, the ''ordinary'' partial Bell polynomial can be defined by the generating function
:<math> \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!}.</math>

Or, equivalently, by series expansion of the ''k''-th power:
:<math>\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. </math>

See also [[Generating function transformation#Powers of an OGF and composition with functions|generating function transformations]] for Bell polynomial generating function expansions of compositions of sequence [[generating functions]] and [[Exponentiation|powers]], [[logarithm]]s, and [[exponential function|exponentials]] of a sequence generating function. Each of these formulas is cited in the respective sections of Comtet.{{Sfn|Comtet|1974}}

===Recurrence relations===

The complete Bell polynomials can be [[Recurrence relation|recurrently]] defined as
:<math> 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}</math>
with the initial value <math>B_0 = 1</math>.

The partial Bell polynomials can also be computed efficiently by a recurrence relation:
:<math> 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})</math>
where
:<math> B_{0,0} = 1; </math>
:<math> B_{n,0} = 0 \text{ for } n \geq 1; </math>
:<math> B_{0,k} = 0 \text{ for } k \geq 1. </math>

In addition:{{sfn|Cvijović|2011}}

:<math>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}).</math>

When <math>1 \le a < n</math>,
:<math>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).</math>

The complete Bell polynomials also satisfy the following recurrence differential formula:{{Sfn|Alexeev|Pologova|Alekseyev|2017|loc=sect. 4.2}}
: <math>
\begin{align}
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{align}
</math>

===Derivatives===

The partial derivatives of the complete Bell polynomials are given by{{Sfn|Bell|1934|loc=identity (5.1) on p. 266}}
: <math> \frac{\partial B_{n}}{\partial x_i} (x_1, \ldots, x_{n}) = \binom{n}{i} B_{n-i}(x_1, \ldots, x_{n-i}).</math>

Similarly, the partial derivatives of the partial Bell polynomials are given by
: <math> \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}).</math>

If the arguments of the Bell polynomials are one-dimensional functions, the chain rule can be used to obtain
: <math> \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)).</math>


===Stirling numbers and Bell numbers===

The value of the Bell polynomial ''B''<sub>''n'',''k''</sub>(''x''<sub>1</sub>,''x''<sub>2</sub>,...) on the sequence of [[factorial]]s equals an unsigned [[Stirling number of the first kind]]:
:<math>B_{n,k}(0!,1!,\dots,(n-k)!)=c(n,k)=|s(n,k)| = \left[{n\atop k}\right].</math>
The sum of these values gives the value of the complete Bell polynomial on the sequence of factorials:
:<math>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!.</math>

The value of the Bell polynomial ''B''<sub>''n'',''k''</sub>(''x''<sub>1</sub>,''x''<sub>2</sub>,...) on the sequence of ones equals a [[Stirling number of the second kind]]:
:<math>B_{n,k}(1,1,\dots,1)=S(n,k)=\left\{{n\atop k}\right\}.</math>
The sum of these values gives the value of the complete Bell polynomial on the sequence of ones:
:<math>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\},</math>
which is the ''n''th [[Bell number]].
:<math>B_{n,k}(1!,2!,\ldots,(n-k+1)!) = \binom{n-1}{k-1} \frac{n!}{k!} = L(n,k)</math>
which gives the [[Lah number]].

===Touchard polynomials===

{{main|Touchard polynomials}}

Touchard polynomial <math>T_n(x) = \sum_{k=0}^n \left\{{n\atop k}\right\}\cdot x^k</math> can be expressed as the value of the complete Bell polynomial on all arguments being ''x'':
: <math>T_n(x) = B_n(x,x,\dots,x).</math>

===Inverse relations===
If we define

:<math>y_n = \sum_{k=1}^n B_{n,k}(x_1,\ldots,x_{n-k+1}),</math>

then we have the inverse relationship

:<math>x_n = \sum_{k=1}^n (-1)^{k-1} (k-1)! B_{n,k}(y_1,\ldots,y_{n-k+1}).</math>
More generally,<ref>{{Cite journal |last1=Chou |first1=W.-S. |last2=Hsu |first2=Leetsch C. |last3=Shiue |first3=Peter J.-S. |date=2006-06-01 |title=Application of Faà di Bruno's formula in characterization of inverse relations |journal=Journal of Computational and Applied Mathematics |language=en |volume=190 |issue=1–2 |pages=151–169 |doi=10.1016/j.cam.2004.12.041|doi-access=free }}</ref><ref>{{Cite journal |last=Chu |first=Wenchang |date=2021-11-19 |title=Bell Polynomials and Nonlinear Inverse Relations |url=https://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i4p24 |journal=The Electronic Journal of Combinatorics |volume=28 |issue=4 |doi=10.37236/10390 |issn=1077-8926|doi-access=free }}</ref> given some function <math>f</math> admitting an inverse <math>g = f^{-1}</math>,<blockquote><math>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}). </math></blockquote>

===Determinant forms===

The complete Bell polynomial can be expressed as [[determinant]]s:

:<math>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}</math>

and

:<math>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}.</math>

===Convolution identity===

For sequences ''x''<sub>''n''</sub>, ''y''<sub>''n''</sub>, ''n'' = 1, 2, ..., define a [[convolution]] by:

:<math>(x \mathbin{\diamondsuit} y)_n = \sum_{j=1}^{n-1} {n \choose j} x_j y_{n-j}.</math>

The bounds of summation are 1 and ''n''&nbsp;−&nbsp;1, not 0 and ''n'' .

Let <math>x_n^{k\diamondsuit}\,</math> be the ''n''th term of the sequence

:<math>\displaystyle\underbrace{x\mathbin{\diamondsuit}\cdots\mathbin{\diamondsuit} x}_{k \text{ factors}}.\,</math>

Then{{Sfn|Cvijović|2011}}

:<math>B_{n,k}(x_1,\dots,x_{n-k+1}) = {x_n^{k\diamondsuit} \over k!}.\,</math>

For example, let us compute <math> B_{4,3}(x_1,x_2) </math>.  We have

:<math> x = ( x_1 \ , \ x_2 \ , \ x_3 \ , \ x_4 \ , \dots ) </math>

:<math> x \mathbin{\diamondsuit} x = ( 0,\  2 x_1^2 \ ,\  6 x_1 x_2 \ , \  8 x_1 x_3 + 6 x_2^2 \ , \dots ) </math>

:<math> x \mathbin{\diamondsuit} x \mathbin{\diamondsuit} x = (  0 \ ,\ 0 \  , \ 6 x_1^3 \ , \ 36 x_1^2 x_2 \ , \dots ) </math>

and thus,

:<math> B_{4,3}(x_1,x_2) = \frac{ ( x \mathbin{\diamondsuit} x \mathbin{\diamondsuit} x)_4 }{3!} = 6 x_1^2 x_2. </math>

==Other identities==

* <math>B_{n,k}(1,2,3,\ldots,n-k+1) = \binom{n}{k} k^{n-k} </math> which gives the [[Idempotence#Idempotent functions|idempotent number]].
* <math>B_{n,k}(\alpha \beta x_1,\alpha \beta^2 x_2, \ldots, \alpha \beta^{n-k+1}x_{n-k+1}) = \alpha^k \beta^n B_{n,k}(x_1,x_2,\ldots,x_{n-k+1})</math>.
* The complete Bell polynomials satisfy the binomial type relation:
*:<math> 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),</math>
*:<math> 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).</math>
:This corrects the omission of the factor <math>(q!)^k</math> in Comtet's book.{{Sfn|Comtet|1974|loc=identity [3l"] on p. 136}}


* Special cases of partial Bell polynomials:

:<math>
\begin{align}
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_kx_{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_2x_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_2x_4 + 2x_3^2) + 105\binom{n}{7}x_1^{n-7}x_2^2x_3 \\
& + 105\binom{n}{8}x_1^{n-8}x_2^4.
\end{align} 
</math>

==Examples==

The first few complete Bell polynomials are:

:<math>
\begin{align}
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 + 6 x_1^2 x_2 + 4 x_1 x_3 + 3 x_2^2 + x_4, \\[8pt]
B_5(x_1,x_2,x_3,x_4,x_5) = {} & x_1^5 + 10 x_2 x_1^3 + 15 x_2^2 x_1 + 10 x_3 x_1^2 + 10 x_3 x_2 + 5 x_4 x_1 + x_5 \\[8pt]
B_6(x_1,x_2,x_3,x_4,x_5,x_6) = {} & x_1^6 + 15 x_2 x_1^4 + 20 x_3 x_1^3 + 45 x_2^2 x_1^2 + 15 x_2^3 + 60 x_3 x_2 x_1 \\
& {} + 15 x_4 x_1^2 + 10 x_3^2 + 15 x_4 x_2 + 6 x_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 + 21 x_1^5 x_2 + 35 x_1^4 x_3 + 105 x_1^3 x_2^2 + 35 x_1^3 x_4 \\
& {} + 210 x_1^2 x_2 x_3 + 105 x_1 x_2^3 + 21 x_1^2 x_5 + 105 x_1 x_2 x_4 \\
& {} + 70 x_1 x_3^2 + 105 x_2^2 x_3 + 7 x_1 x_6 + 21 x_2 x_5 + 35 x_3 x_4 + x_7. 
\end{align}</math>

==Applications==

===Faà di Bruno's formula===
{{main|Faà di Bruno's formula}}

[[Faà di Bruno's formula]] may be stated in terms of Bell polynomials as follows:

:<math>{d^n \over dx^n} f(g(x)) = \sum_{k=1}^n f^{(k)}(g(x)) B_{n,k} \left(g'(x),g''(x), \dots, g^{(n-k+1)}(x)\right).</math>

Similarly, a power-series version of Faà di Bruno's formula may be stated using Bell polynomials as follows.  Suppose

:<math>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.</math>

Then

:<math>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.</math>

In particular, the complete Bell polynomials appear in the exponential of a [[formal power series]]:

:<math>\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,</math>
which also represents the [[exponential generating function]] of the complete Bell polynomials on a fixed sequence of arguments <math>a_1, a_2, \dots</math>.

===Reversion of series===
{{main|Lagrange inversion theorem}}

Let two functions ''f'' and ''g'' be expressed in formal [[power series]] as

:<math>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!},</math>

such that ''g'' is the compositional inverse of ''f'' defined by ''g''(''f''(''w'')) = ''w'' or ''f''(''g''(''z'')) = ''z''. If ''f''<sub>0</sub> = 0 and ''f''<sub>1</sub> ≠ 0, then an explicit form of the coefficients of the inverse can be given in term of Bell polynomials as{{sfn|Charalambides|2002|p=437|loc=Eqn (11.43)}}

:<math> 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, </math>

with <math> \hat{f}_k = \frac{f_{k+1}}{(k+1)f_{1}},</math> and <math>n^{\bar{k}} = n(n+1)\cdots (n+k-1) </math> is the rising factorial, and <math>g_1 = \frac{1}{f_{1}}. </math>

===Asymptotic expansion of Laplace-type integrals===
Consider the integral of the form

:<math>I(\lambda) = \int_a^b e^{-\lambda f(x)} g(x) \, \mathrm{d}x, </math>

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''&nbsp;=&nbsp;''a''. Assume that as ''x''&nbsp;→&nbsp;''a''<sup>+</sup>,

:<math> f(x) \sim f(a) + \sum_{k=0}^\infty a_k (x-a)^{k+\alpha}, </math>
:<math> g(x) \sim \sum_{k=0}^\infty b_k (x-a)^{k+\beta-1}, </math>

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

:<math> 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, </math>

where the coefficients ''c<sub>n</sub>'' are expressible in terms of ''a<sub>n</sub>'' and ''b<sub>n</sub>'' using partial ''ordinary'' Bell polynomials, as given by Campbell–Froman–Walles–Wojdylo formula:

:<math> 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}). </math>

===Symmetric polynomials=== 
{{main|Newton's identities}}
The [[elementary symmetric polynomial]] <math>e_n</math> and the [[power sum symmetric polynomial]] <math>p_n</math> can be related to each other using Bell polynomials as:
: <math>
\begin{align}
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{align}
</math>
: <math>
\begin{align}
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{align}
</math>


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: 
: <math> \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).</math>

===Cycle index of symmetric groups===
{{main|Cycle index}}

The [[cycle index]] of the [[symmetric group]] <math>S_n</math> can be expressed in terms of complete Bell polynomials as follows:
:<math> Z(S_n) = \frac{B_n(0!\,a_1, 1!\,a_2, \dots, (n-1)!\,a_n)}{n!}.</math>

===Moments and cumulants===

The sum

:<math>\mu_n' = B_n(\kappa_1,\dots,\kappa_n)=\sum_{k=1}^n B_{n,k}(\kappa_1,\dots,\kappa_{n-k+1})</math>

is the ''n''th raw [[moment (mathematics)|moment]] of a [[probability distribution]] whose first ''n'' [[cumulant]]s are ''κ''<sub>1</sub>, ..., ''κ''<sub>''n''</sub>.  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

:<math>\kappa_n = \sum_{k=1}^n (-1)^{k-1} (k-1)! B_{n,k}(\mu'_1,\ldots,\mu'_{n-k+1}).</math>

===Hermite polynomials===
{{main|Hermite polynomials}}

[[Hermite polynomials]] can be expressed in terms of Bell polynomials as

:<math>\operatorname{He}_n(x) = B_n(x,-1,0,\ldots,0),</math>

where ''x''<sub>''i''</sub> = 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

:<math>\exp \left(xt-\frac{t^2}{2} \right) = \sum_{n=0}^\infty \operatorname{He}_n(x) \frac {t^n}{n!}</math>

with that of Bell polynomials.

===Representation of polynomial sequences of binomial type===

For any sequence ''a''<sub>1</sub>, ''a''<sub>2</sub>, …, ''a''<sub>''n''</sub> of scalars, let

:<math>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.</math>

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

:<math>p_n(x+y)=\sum_{k=0}^n {n \choose k} p_k(x) p_{n-k}(y).</math>
:'''Example:''' For ''a''<sub>1</sub> = … = ''a''<sub>''n''</sub> = 1, the polynomials <math>p_n(x)</math> 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

:<math>h(x)=\sum_{k=1}^\infty {a_k \over k!} x^k,</math>

then for all ''n'',

:<math>h^{-1}\left( {d \over dx}\right) p_n(x) = n p_{n-1}(x).</math>

==Software==

Bell polynomials are implemented in:
* [[Mathematica]] as [http://reference.wolfram.com/mathematica/ref/BellY.html BellY]
* [[Maple (software)|Maple]] as [http://www.maplesoft.com/support/help/Maple/view.aspx?path=BellB IncompleteBellB]
* [[SageMath]] as [http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/combinat.html#sage.combinat.combinat.bell_polynomial bell_polynomial]

==See also==

* [[Bell matrix]]
* [[Exponential formula]]

== Notes ==
{{Reflist|colwidth=30em}}

==References==
{{refbegin}}
*{{ cite journal |first1=M. |last1=Abbas |first2=S. |last2=Bouroubi |title=On new identities for Bell's polynomial |journal=Discrete Math. |year=2005 |volume=293 |issue=1–3 |pages=5–10 |mr=2136048 |doi=10.1016/j.disc.2004.08.023|doi-access=free }}
* {{cite journal |last1=Alexeev |first1=N. |last2=Pologova |first2=A. |last3=Alekseyev |first3=M. A. |title=Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs |journal=Journal of Computational Biology |volume=24 |issue=2 |year=2017 |pages=93–105 |doi=10.1089/cmb.2016.0190 |pmid=28045556 |arxiv=1503.05285|s2cid=9678733 }}
* {{cite book |first=G. E. | last=Andrews | author-link=George Andrews (mathematician) | title=The Theory of Partitions | series=Cambridge Mathematical Library | publisher=[[Cambridge University Press]] | year=1998 | edition=1st pbk | isbn=0-521-63766-X | pages=204–211 }} 
* {{cite journal |last=Bell |first=E. T. |author-link=Eric Temple Bell |title=Partition Polynomials | jstor=1967979 |journal=[[Annals of Mathematics]] |volume=29 |issue=1/4 |year=1927–1928 |pages=38–46 |doi=10.2307/1967979 | mr=1502817 }}
* {{cite journal |last=Bell |first=E. T. |author-link=Eric Temple Bell |title=Exponential Polynomials | jstor=1968431 |journal=[[Annals of Mathematics]] |volume=35 |issue=2 |year=1934 |pages=258–277 |doi=10.2307/1968431 | mr=1503161 }}
* {{cite journal |first=K. N. |last=Boyadzhiev |title=Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals |journal=[[Abstract and Applied Analysis]] |volume=2009 |pages=1–18 |year=2009 |doi=10.1155/2009/168672|arxiv=0909.0979 |bibcode=2009AbApA2009....1B |s2cid=1608664 |doi-access=free }} (contains also elementary review of the concept Bell-polynomials)
* {{cite book |first=C. A. |last=Charalambides |title=Enumerative Combinatorics |publisher=Chapman & Hall / CRC |year=2002 |isbn=9781584882909 |pages=632}}
* {{cite book |first=L. |last=Comtet |title=Advanced Combinatorics: The Art of Finite and Infinite Expansions |publisher=Reidel Publishing Company |place=Dordrecht, Holland / Boston, U.S. |year=1974 |url=https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics |access-date=2019-07-02 |archive-url=https://web.archive.org/web/20170601062056/https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics |archive-date=2017-06-01 |url-status=live }}
* {{cite journal|last=Cvijović |first=D. |title=New identities for the partial Bell polynomials |journal=Applied Mathematics Letters |year=2011 |volume=24 |issue=9 |pages=1544–1547 |doi=10.1016/j.aml.2011.03.043 |s2cid=45311678 |url=http://vinar.vin.bg.ac.rs//bitstream/id/12791/4374.pdf |access-date=2020-06-05 |archive-url=https://web.archive.org/web/20200309144314/http://vinar.vin.bg.ac.rs//bitstream/id/12791/4374.pdf|archive-date=2020-03-09|url-status=live}}
* {{cite journal |first1=M. |last1=Griffiths |title=Families of sequences from a class of multinomial sums |journal=Journal of Integer Sequences |url=http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Griffiths/griffiths20.html |year=2012 |mr=2872465 |volume=15 |pages=Article 12.1.8 |access-date=2012-06-27 |archive-url=https://web.archive.org/web/20140502084205/https://cs.uwaterloo.ca/journals/JIS/VOL15/Griffiths/griffiths20.html |archive-date=2014-05-02 |url-status=live }}
* {{cite arXiv |first=V. V. |last=Kruchinin |year=2011|eprint=1104.5065 |title=Derivation of Bell Polynomials of the Second Kind|class=math.CO }}
* {{cite journal |first1=S. |last1=Noschese |first2=P. E. |last2=Ricci |title=Differentiation of Multivariable Composite Functions and Bell Polynomials |journal=Journal of Computational Analysis and Applications | volume=5 |issue=3 |pages=333–340 |year=2003 |doi=10.1023/A:1023227705558|s2cid=118361207 }}
* {{cite book |last=Roman |first=S. |author-link=Steven Roman |title=The Umbral Calculus |publisher=[[Dover Publications]] |year=2013 |isbn=9780486153421 |pages=208}}
* {{cite journal |first1=V. G. |last1=Voinov |first2=M. S. |last2=Nikulin |title=On power series, Bell polynomials, Hardy–Ramanujan–Rademacher problem and its statistical applications |journal= Kybernetika | volume=30 |issue=3 |pages=343–358 |year=1994 |issn=0023-5954}}
{{refend}}

{{DEFAULTSORT:Bell Polynomials}}
[[Category:Enumerative combinatorics]]
[[Category:Polynomials]]