Bell polynomial

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)