Exponential formula

Here is a purely algebraic statement, as a first introduction to the combinatorial use of the formula.

For any formal power series of the form

$${\displaystyle 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

$${\displaystyle \exp f(x)=e^{f(x)}=\sum _{n=0}^{\infty }{b_{n} \over n!}x^{n},\,}$$

where

$${\displaystyle b_{n}=\sum _{\pi =\left\{\,S_{1},\,\dots ,\,S_{k}\,\right\}}a_{\left|S_{1}\right|}\cdots a_{\left|S_{k}\right|},}$$

and the index ${\displaystyle \pi }$ runs through the list of all partitions ${\displaystyle \{S_{1},\ldots ,S_{k}\}}$ of the set ${\displaystyle \{1,\ldots ,n\}}$. (When ${\displaystyle k=0,}$ the product is empty and by definition equals ${\displaystyle 1}$.)

Formula in other expressions

One can write the formula in the following form:

$${\displaystyle b_{n}=B_{n}(a_{1},a_{2},\dots ,a_{n}),}$$

and thus

$${\displaystyle \exp \left(\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\right)=\sum _{n=0}^{\infty }{B_{n}(a_{1},\dots ,a_{n}) \over n!}x^{n},}$$

where ${\displaystyle B_{n}(a_{1},\ldots ,a_{n})}$ is the ${\displaystyle n}$th complete Bell polynomial.

Alternatively, the exponential formula can also be written using the cycle index of the symmetric group, as follows:

$${\displaystyle \exp \left(\sum _{n=1}^{\infty }a_{n}{x^{n} \over n}\right)=\sum _{n=0}^{\infty }Z_{n}(a_{1},\dots ,a_{n})x^{n},}$$

where ${\displaystyle Z_{n}}$ stands for the cycle index polynomial, for the symmetric group ${\displaystyle S_{n}}$ defined as:

$${\displaystyle Z_{n}(x_{1},\cdots ,x_{n})={\frac {1}{n!}}\sum _{\sigma \in S_{n}}x_{1}^{\sigma _{1}}\cdots x_{n}^{\sigma _{n}}}$$

and ${\displaystyle \sigma _{j}}$ denotes the number of cycles of ${\displaystyle \sigma }$ of size ${\displaystyle j\in \{1,\cdots ,n\}}$. This is a consequence of the general relation between ${\displaystyle Z_{n}}$ and Bell polynomials:

$${\displaystyle Z_{n}(x_{1},\dots ,x_{n})={1 \over n!}B_{n}(0!\,x_{1},1!\,x_{2},\dots ,(n-1)!\,x_{n}).}$$

In applications, the numbers ${\displaystyle a_{n}}$ count the number of some sort of "connected" structure on an ${\displaystyle n}$-point set, and the numbers ${\displaystyle b_{n}}$ count the number of (possibly disconnected) structures. The numbers ${\displaystyle b_{n}/n!}$ count the number of isomorphism classes of structures on ${\displaystyle n}$ points, with each structure being weighted by the reciprocal of its automorphism group, and the numbers ${\displaystyle a_{n}/n!}$ count isomorphism classes of connected structures in the same way.

• ${\displaystyle b_{3}=B_{3}(a_{1},a_{2},a_{3})=a_{3}+3a_{2}a_{1}+a_{1}^{3},}$ because there is one partition of the set ${\displaystyle \{1,2,3\}}$ that has a single block of size ${\displaystyle 3}$, there are three partitions of ${\displaystyle \{1,2,3\}}$ that split it into a block of size ${\displaystyle 2}$ and a block of size ${\displaystyle 1}$, and there is one partition of ${\displaystyle \{1,2,3\}}$ that splits it into three blocks of size ${\displaystyle 1}$. This also follows from ${\displaystyle Z_{3}(a_{1},a_{2},a_{3})={1 \over 6}(2a_{3}+3a_{1}a_{2}+a_{1}^{3})={1 \over 6}B_{3}(a_{1},a_{2},2a_{3})}$, since one can write the group ${\displaystyle S_{3}}$ as ${\displaystyle S_{3}=\{(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)\}}$ , using cyclic notation for permutations.
• If ${\displaystyle b_{n}=2^{n(n-1)/2}}$ is the number of graphs whose vertices are a given ${\displaystyle n}$-point set, then ${\displaystyle a_{n}}$ is the number of connected graphs whose vertices are a given ${\displaystyle n}$-point set.
• There are numerous variations of the previous example where the graph has certain properties: for example, if ${\displaystyle b_{n}}$ counts graphs without cycles, then ${\displaystyle a_{n}}$ counts trees (connected graphs without cycles).
• If ${\displaystyle b_{n}}$ counts directed graphs whose edges (rather than vertices) are a given ${\displaystyle n}$ point set, then ${\displaystyle a_{n}}$ counts connected directed graphs with this edge set.
• In quantum field theory and statistical mechanics, the partition functions ${\displaystyle Z}$, or more generally correlation functions, are given by a formal sum over Feynman diagrams. The exponential formula shows that ${\displaystyle \ln(Z)}$ can be written as a sum over connected Feynman diagrams, in terms of connected correlation functions.

• Surjection of Fréchet spaces – Characterization of surjectivity

• Stanley, Richard P. (1999), Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, ISBN 978-0-521-56069-6, MR 1676282, ISBN 978-0-521-78987-5 Chapter 5 page 3