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 we have where and the index \pi runs through all partitions of the set . (When k = 0, the product is empty and by definition equals 1.)

Formula in other expressions

One can write the formula in the following form: and thus where is the nth complete Bell polynomial. Alternatively, the exponential formula can also be written using the cycle index of the symmetric group, as follows:where Z_n stands for the cycle index polynomial for the symmetric group S_n, defined as:and \sigma_j denotes the number of cycles of \sigma of size. This is a consequence of the general relation between Z_n and Bell polynomials:

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