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.

Statement

For any formal power series of the form
we have
where
and the index runs through the list of all partitions of the set.
One can write the formula in the following form:
and thus
where Bn is the nth complete Bell polynomial.

Examples

In applications, the numbers an often count the number of some sort of "connected" structure on an n-point set, and the numbers bn count the number of structures. The numbers bn/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 an/n! count isomorphism classes of connected structures in the same way.
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 log can be written as a sum over connected Feynman diagrams, in terms of connected correlation functions.