Exponential formula

In combinatorial mathematics, the exponential formula 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
we have
where
and the index runs through all partitions of the set
.

Other expressions

One can write the exponential formula in the following form:
The exponential formula can also be written as follows:

Combinatorial interpretation

In combinatorial applications, the numbers count the number of some sort of "connected" structure on an -point set, and the numbers count the number of structures. The numbers count the number of isomorphism classes of structures on points, with each structure being weighted by the reciprocal of its automorphism group, and the numbers count isomorphism classes of connected structures in the same way.

Examples

because there is one partition of the set that has a single block of size, there are three partitions of that split it into a block of size and a block of size, and there is one partition of that splits it into three blocks of size. This also follows from, since one can write the group as, using cyclic notation for permutations.
If is the number of graphs whose vertices are a given -point set, then is the number of connected graphs whose vertices are a given -point set.
There are numerous variations of the previous example where the graph has certain properties: for example, if counts graphs without cycles, then counts trees.
If counts directed graphs whose are a given point set, then counts connected directed graphs with this edge set.
In quantum field theory and statistical mechanics, the partition functions, or more generally correlation functions, are given by a formal sum over Feynman diagrams. The exponential formula shows that can be written as a sum over connected Feynman diagrams, in terms of connected correlation functions.