Namespaces
Variants
Actions

Bell polynomial

From Encyclopedia of Mathematics
Revision as of 10:58, 29 May 2020 by Ulf Rehmann (talk | contribs) (tex encoded by computer)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


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