Exponential formula

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|},$

the index π running through the list of all partitions { B₁, ..., B_k } of the set { 1, ..., n }. For example, we have

$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.

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

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.

Categories: Exponentials