In combinatorial mathematics, the exponential formula (called the polymer expansion in physics) states that the exponential generating function for structures on finite sets is the exponential of the exponential generating function for connected structures. The exponential formula is a power series version of a special case of Faà di Bruno's formula.

Algebraic statement

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

f(x) = a_1 x + a_2 \frac{x^2}{2} + a_3 \frac{x^3}{6} + \dots + a_n \frac{x^n}{n!} + \dots

we have

\exp f(x) = e^{f(x)} = \sum_{n=0}^\infty b_n \frac{x^n}{n!}

where

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 \pi runs through all partitions \{ S_1, \ldots, S_k \} of the set \{ 1,\ldots, n \}. (When k = 0, the product is empty and by definition equals 1.)

Other expressions

  • One can write the exponential formula in the following form
b_n = B_n(a_1, a_2, \dots, a_n)
and thus
\exp\left( \sum_{n=1}^\infty a_n \frac{x^n}{n!} \right) = \sum_{n=0}^\infty B_n(a_1,\dots,a_n) \frac{x^n}{n!}
where B_n(a_1, \ldots, a_n) is the nth complete Bell polynomial.
  • The exponential formula can also be written as follows:
\exp\left( \sum_{n=1}^\infty a_n \frac{x^n}{n} \right) = \sum_{n=0}^\infty Z_n(a_1, \dots, a_n) x^n
where Z_n stands for the cycle index polynomial for the symmetric group S_n, defined as:
Z_n(a_1, \dots, a_n) = \frac{1}{n!} \sum_{\sigma\in S_n} a_1^{\sigma_1} \cdots a_n^{\sigma_n}
and \sigma_j denotes the number of cycles of \sigma of size j \in \{1, \dots, n\}. This is a consequence of the general relation between Z_n and Bell polynomials:
n! Z_n(a_1, \dots, a_n) = B_n(0!\,a_1, 1!\,a_2, \dots, (n-1)!\,a_n).

Combinatorial interpretation

In combinatorial applications, the numbers a_n count the number of some sort of "connected" structure on an n-point set, and the numbers b_n count the number of (possibly disconnected) structures (see combinatorial species). The numbers b_n/n! count the number of isomorphism classes of structures on n points, with each structure being weighted by the reciprocal of its automorphism group, and the numbers a_n/n! count isomorphism classes of connected structures in the same way.

Examples

  • 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 \{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 also follows from Z_3 (a_1,a_2,a_3) = {1 \over 6}(2 a_3 + 3 a_1 a_2 + a_1^3) = {1 \over 6} B_3 (a_1, a_2, 2 a_3), since one can write the group S_3 as S_3 = \{ (1)(2)(3), (1)(23), (2)(13), (3)(12), (123), (132) \}, using cyclic notation for permutations.
  • If b_n = 2^{n(n-1)/2} is the number of graphs whose vertices are a given n-point set, then a_n is the number of connected graphs whose vertices are a given n-point set.
  • There are numerous variations of the previous example where the graph has certain properties: for example, if b_n counts graphs without cycles, then a_n counts trees (connected graphs without cycles).
  • If b_n counts directed graphs whose edges (rather than vertices) are a given n point set, then a_n counts connected directed graphs with this edge set.
  • In quantum field theory and statistical mechanics, the partition functions Z, or more generally correlation functions, are given by a formal sum over Feynman diagrams. The exponential formula shows that \ln(Z) can be written as a sum over connected Feynman diagrams, in terms of connected correlation functions.

References