Bell polynomial

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

The Bell polynomials (studied extensively by E.T. Bell [a2]) arise naturally from differentiating a composite function $n$ times, but in this context they predate Bell since they are implicit in the work of F. Faà di Bruno [a4]. Accounts of Faà di Bruno's formula, however, often fail to mention any connection with Bell polynomials. The polynomials also occur in other places without being referred to by name; in [a1] (Table 24.2), for example, the numbers $M _ {3}$ are coefficients of partial Bell polynomials, but are not identified as such.

Suppose that $h ( t ) = f ( g ( t ) )$ and let

$$h _ {n} = { \frac{d ^ {n} h }{d t ^ {n} } } , f _ {n} = { \frac{d ^ {n} f }{d g ^ {n} } } , g _ {n} = { \frac{d ^ {n} g }{d t ^ {n} } } ;$$

then by repeated application of the chain rule:

$$h _ {0} = f _ {0} , h _ {1} = f _ {1} g _ {1} , h _ {2} = f _ {1} g _ {2} + f _ {2} g _ {1} ^ {2} ,$$

$$h _ {3} = f _ {1} g _ {3} + f _ {2} ( 3g _ {1} g _ {2} ) + f _ {3} g _ {1} ^ {3} ,$$

$$h _ {4} = f _ {1} g _ {4} + f _ {2} ( 3g _ {2} ^ {2} + 4g _ {1} g _ {3} ) + f _ {3} ( 6g _ {1} ^ {2} g _ {2} ) + f _ {4} g _ {1} ^ {4} .$$

In general,

$$\tag{a1 } h _ {n} = \sum _ {k = 1 } ^ { n } f _ {k} B _ {n,k } ( g _ {1} \dots g _ {n - k + 1 } ) ,$$

where $B _ {n,k }$ is a homogeneous polynomial of degree $k$ and weight $n$ in the $g _ {m}$, known as a (partial) Bell polynomial (see [a3] for a table for $1 \leq k \leq n \leq 12$); it has integral coefficients. Because of the homogeneity, for fixed $n$ all $B _ {n,k }$( $k = 1 \dots n$) can be determined uniquely even if the $f _ {k}$ are omitted. Hence the (complete) Bell polynomial $Y _ {n}$ is usually defined for $n \geq 1$ by

$$Y _ {n} ( g _ {1} \dots g _ {n} ) = \sum _ {k = 1 } ^ { n } B _ {n,k } ( g _ {1} \dots g _ {n - k + 1 } ) .$$

In [a7], however, the term Bell polynomial is used for

$$A _ {n} ( f;g _ {1} , \dots,g _ {n - k + 1 } ) = h _ {n} ,$$

so the $f _ {k}$ are included in the definition.

The following definitions are also made: $B _ {0,0 } = 1$, $B _ {0,k } = 0$( $k \geq 1$), $Y _ {0} = 1$.

Although the $g _ {n}$ were introduced as derivatives, the Bell polynomials themselves, considered purely as polynomials in the variables $g _ {1} ,g _ {2} , \dots$ are independent of the initial functions $g ( t )$ and $f ( g )$. Hence information can be deduced from special choices such as $f ( g ) = e ^ {g}$, which gives

$$Y _ {n} ( g _ {1} , \dots,g _ {n} ) = e ^ {- g } { \frac{d ^ {n} e ^ {g} }{d t ^ {n} } } .$$

An alternative approach which gives the same polynomials $B _ {n,k }$ is adopted in [a3], where they are defined as coefficients in the expansion of the two-variable generating function

$$\Phi ( t,u ) = { \mathop{\rm exp} } \left ( u \sum _ {m = 1 } ^ \infty { \frac{g _ {m} t ^ {m} }{m! } } \right ) =$$

$$= 1 + \sum _ {n = 1 } ^ \infty \sum _ {k = 1 } ^ { n } B _ {n,k } ( g _ {1} , \dots,g _ {n - k + 1 } ) { \frac{u ^ {k} t ^ {n} }{n! } } .$$

This approach obviates the earlier assumption that the $g _ {m}$ are derivatives.

The generating function for the complete polynomials is

$$\Phi ( t,1 ) = { \mathop{\rm exp} } \left ( \sum _ {m = 1 } ^ \infty { \frac{g _ {m} t ^ {m} }{m! } } \right ) =$$

$$= 1 + \sum _ {n = 1 } ^ \infty Y _ {n} ( g _ {1} , \dots,g _ {n} ) { \frac{t ^ {n} }{n! } } .$$

Explicit formulas are known for Bell polynomials and they are examples of partition polynomials (multivariable polynomials which can be expressed as a sum of monomials, where the sum is over a set of partitions of $n$; cf. also Partition). The partial polynomial

$$B _ {n,k } ( g _ {1} , \dots,g _ {n - k + 1 } ) =$$

$$= \sum { \frac{n! }{c _ {1} ! \dots c _ {n - k + 1 } ! } } \left ( { \frac{g _ {1} }{1! } } \right ) ^ {c _ {1} } \dots \left ( { \frac{g _ {n - k + 1 } }{( n - k + 1 ) ! } } \right ) ^ {c _ {n - k + 1 } } ,$$

where the sum is over all partitions of $n$ into exactly $k$ non-negative parts, i.e., over all solutions in non-negative integers $c _ {r}$ of the two equations

$$c _ {1} + 2c _ {2} + \dots + ( n - k + 1 ) c _ {n - k + 1 } = n,$$

$$c _ {1} + c _ {2} + \dots + c _ {n - k + 1 } = k.$$

Since, for each fixed $k$, there can be no parts of size greater than $n - k + 1$, the formula is often stated in the simpler looking, but equivalent, form (where necessarily $c _ {n - k + 2 } = \dots = c _ {n} = 0$):

$$\tag{a2 } B _ {n,k } ( g _ {1} , \dots,g _ {n - k + 1 } ) =$$

$$= \sum { \frac{n! }{c _ {1} ! \dots c _ {n} ! } } \left ( { \frac{g _ {1} }{1! } } \right ) ^ {c _ {1} } \dots \left ( { \frac{g _ {n} }{n! } } \right ) ^ {c _ {n} } ,$$

where the sum is over all solutions in non-negative integers of the equations

$$c _ {1} + 2c _ {2} + \dots + nc _ {n} = n,$$

$$c _ {1} + c _ {2} + \dots + c _ {n} = k.$$

The complete polynomial

$$Y _ {n} ( g _ {1} , \dots,g _ {n} ) = \sum { \frac{n! }{c _ {1} ! \dots c _ {n} ! } } \left ( { \frac{g _ {1} }{1! } } \right ) ^ {c _ {1} } \dots ( { \frac{g _ {n} }{n! } } ) ^ {c _ {n} } ,$$

where the sum is over all partitions of $n$ into arbitrarily many non-negative parts, i.e., over all non-negative integer solutions of the single equation

$$c _ {1} + 2c _ {2} + \dots + nc _ {n} = n.$$

There are many recurrence relations for Bell polynomials, as well as formulas connecting them with other special polynomials and numbers; the following is a small selection, and others may be found in [a3], [a7], [a8].

$$kB _ {n,k } ( g _ {1} , \dots,g _ {n - k + 1 } ) =$$

$$= \sum _ {r = k - 1 } ^ { {n } - 1 } \left ( \begin{array}{c} n \\ r \end{array} \right ) g _ {n - r } B _ {r,k - 1 } ( g _ {1} \dots g _ {r - k + 2 } ) ,$$

$$B _ {n,k } ( 1, \dots,n - k + 1 ) = \left ( \begin{array}{c} n \\ k \end{array} \right ) k ^ {n - k } ,$$

$$B _ {n,k } ( 0!, \dots, ( n - k ) ! ) = \left | {s ( n,k ) } \right | ,$$

$$B _ {n,k } ( 1, \dots,1 ) = S ( n,k ) ,$$

where $s ( n,k )$ and $S ( n,k )$ are Stirling numbers of the first and second kinds (cf. Combinatorial analysis), respectively;

$$B _ {n,k } ( 1!, \dots, ( n - k + 1 ) ! ) = \left | {L _ {n,k } } \right | ,$$

where $L _ {n,k }$ is the Lah number;

$$Y _ {n} ( 1, \dots,1 ) = B _ {n} ,$$

where $B _ {n}$ are the Bell numbers.

Combining equations (a1) and (a2) gives Faà di Bruno's formula for the $n$ th derivative of a composite function:

$${ \frac{d ^ {n} }{d t ^ {n} } } f ( g ( t ) ) =$$

$$= \sum { \frac{n! }{c _ {1} ! \dots c _ {n} ! } } { \frac{d ^ {k} f }{d g ^ {k} } } \left ( { \frac{g ^ \prime }{1! } } \right ) ^ {c _ {1} } \dots \left ( { \frac{g ^ {( n ) } }{n! } } \right ) ^ {c _ {n} } ,$$

summed over all solutions in non-negative integers of

$$c _ {1} + 2c _ {2} + \dots + nc _ {n} = n,$$

$$c _ {1} + c _ {2} + \dots + c _ {n} = k.$$

(For a generalization to functions of several variables, see [a5].)

The formula can be used, in particular, to express functions of power series as power series. If

$$g ( t ) = \sum _ {n = 0 } ^ \infty { \frac{a _ {n} t ^ {n} }{n! } }$$

and

$$h ( t ) = f ( g ( t ) ) = \sum _ {n = 0 } ^ \infty { \frac{b _ {n} t ^ {n} }{n! } } ,$$

then

$$a _ {n} = g ^ {( n ) } ( 0 ) , b _ {n} = h ^ {( n ) } ( 0 ) ,$$

and Faà di Bruno's formula can be used to find $b _ {n}$. For example, if $f ( g ) = { \mathop{\rm ln} } g$, then

$$f ^ {( k ) } = ( - 1 ) ^ {k - 1 } ( k - 1 ) !g ^ {- k } \quad ( k \geq 1 ) .$$

Hence, applying the formula and evaluating the result at $t = 0$ gives

$$\tag{a3 } b _ {n} = h ^ {( n ) } ( 0 ) =$$

$$= \sum _ {k = 1 } ^ { n } ( - 1 ) ^ {k - 1 } ( k - 1 ) ! a _ {0} ^ {- k } B _ {n,k } ( a _ {1} , \dots ,a _ {n - k + 1 } ) { \frac{t ^ {n} }{n! } } .$$

Thus, provided that $a _ {0} > 0$,

$${ \mathop{\rm ln} } \left ( \sum _ {n = 0 } ^ \infty { \frac{a _ {n} t ^ {n} }{n! } } \right ) = { \mathop{\rm ln} } a _ {0} +$$

$$+ \sum _ {n = 1 } ^ \infty \sum _ {k = 1 } ^ { n } ( - 1 ) ^ {k - 1 } ( k - 1 ) ! a _ {0} ^ {- k } B _ {n,k } ( a _ {1} , \dots ,a _ {n - k + 1 } ) { \frac{t ^ {n} }{n! } } .$$

A special case of (a3) is used [a6] to express the cumulants (semi-invariants, cf. Semi-invariant) $\kappa _ {n}$ of a probability distribution $\{ p _ {0} ,p _ {1} , \dots \}$ in terms of its moments (cf. Moment)

$$m _ {n} = \sum _ {r = 0 } ^ \infty r ^ {n} p _ {r} \quad ( n \geq 1 ) ,$$

$$m _ {0} = \sum _ {r = 0 } ^ \infty p _ {r} = 1.$$

The probability generating function of the distribution is

$$G ( z ) = \sum _ {r = 0 } ^ \infty p _ {r} z ^ {r} ,$$

and it is easy to show that

$$G ( e ^ {t} ) = \sum _ {n = 0 } ^ \infty { \frac{m _ {n} t ^ {n} }{n! } } .$$

The cumulants $\kappa _ {n}$( $n \geq 1$) and their exponential generating function $L ( t )$ are defined in terms of $G ( e ^ {t} )$ by

$$L ( t ) = \sum _ {n = 1 } ^ \infty { \frac{\kappa _ {n} t ^ {n} }{n! } } = { \mathop{\rm ln} } G ( e ^ {t} ) = { \mathop{\rm ln} } \sum _ {n = 0 } ^ \infty { \frac{m _ {n} t ^ {n} }{n! } } .$$

Since $m _ {0} = 1$, it follows from (a3) that

$$\kappa _ {n} = \sum _ {k = 1 } ^ { n } ( - 1 ) ^ {k - 1 } ( k - 1 ) ! B _ {n,k } ( m _ {1} \dots m _ {n - k + 1 } ) .$$

Similarly, starting from

$$G ( e ^ {t} ) = \sum _ {n = 0 } ^ \infty { \frac{m _ {n} t ^ {n} }{n! } } = e ^ {L ( t ) } = { \mathop{\rm exp} } \left ( \sum _ {n = 1 } ^ \infty { \frac{\kappa _ {n} t ^ {n} }{n! } } \right ) ,$$

and applying Faà di Bruno's formula with $f ( g ) = e ^ {g}$ and $g ( t ) = \sum { {\kappa _ {n} t ^ {n} } / {n! } }$( and noting that in this case $h ^ {( k ) } ( 0 ) = 1$ for all $k \geq 1$), the inverse relation expressing moments in terms of cumulants reduces to

$$m _ {n} = Y _ {n} ( \kappa _ {1} , \dots, \kappa _ {n} ) .$$

References

 [a1] M. Abramowitz, I. Stegun, "Handbook of mathematical functions" , Dover, reprint (1965) [a2] E.T. Bell, "Exponential polynomials" Ann. of Math. , 35 (1934) pp. 258–277 [a3] L. Comtet, "Advanced combinatorics" , Reidel (1974) [a4] F. Faà di Bruno, "Note sur une nouvelle formule du calcul différentiel" Quart. J. Math. , 1 (1855) pp. 359–360 [a5] I.J. Good, "The multivariate saddlepoint method and chi-squared for the multinomial distribution" Ann. Math. Stat. , 32 (1961) pp. 535–548 [a6] E. Lukács, "Applications of Faà di Bruno's formula in mathematical statistics" Amer. Math. Monthly , 62 (1955) pp. 340–348 [a7] J. Riordan, "Combinatorial identities" , Wiley (1968) [a8] S. Roman, "The umbral calculus" , Acad. Press (1984)
How to Cite This Entry:
Bell polynomial. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bell_polynomial&oldid=46007
This article was adapted from an original article by E.K. Lloyd (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article