Exponential formula

From Wikipedia, the free encyclopedia

In combinatorial mathematics, the exponential formula states that for any formal power series of the form

f(x)=a_1 x+{a_2 \over 2}x^2+{a_3 \over 6}x^3+\cdots+{a_n \over n!}x^n+\cdots\,

we have

\exp f(x)=e^{f(x)}=1+\sum_{n=1}^\infty {b_n \over n!}x^n,\,

where

b_n=\sum_{\pi=\left\{\,B_1,\,\dots,\,B_k\,\right\}} a_{\left|B_1\right|}\cdots a_{\left|B_k\right|},

and the index π runs through the list of all partitions { B1, ..., Bk } of the set { 1, ..., n }. For example,

b_3=a_3+3a_2 a_1 + a_1^3,\,

because there is one partition of the set { 1, 2, 3 } that has a single block of size 3, there are three partitions of { 1, 2, 3 } that split it into a block of size 2 and a block of size 1, and there is one partition of { 1, 2, 3 } that splits it into three blocks of size 1. This polynomial in the three variables a1, a2, a3 is a Bell polynomial.

Essentially, the exponential formula is a power-series version of a special case of Faà di Bruno's formula.

[edit] Bell polynomials

One can write the formula in the following form, where Bn(a1, ..., an) is the nth complete Bell polynomial:

\exp\left(\sum_{n=1}^\infty {a_n \over n!} x^n \right) =1 + \sum_{n=0}^\infty {B_n(a_1,\dots,a_n) \over n!} x^n.

[edit] References

See Chapter 5 of Enumerative Combinatorics, Volumes 1 and 2, Richard P. Stanley, Cambridge University Press, 1997 and 1999, ISBN 0-521-55309-1N.