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

edit

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  . (When   the product is empty and by definition equals  .)

Formula in other expressions

edit

One can write the formula in the following form:   and thus   where   is the  th complete Bell polynomial.

Alternatively, the exponential formula can also be written using the cycle index of the symmetric group, as follows: where   stands for the cycle index polynomial for the symmetric group  , defined as: and   denotes the number of cycles of   of size  . This is a consequence of the general relation between   and Bell polynomials: 

Combinatorial interpretation

edit

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 (possibly disconnected) 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

edit
  •   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 (connected graphs without cycles).
  • If   counts directed graphs whose edges (rather than vertices) 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.

See also

edit

References

edit
  • 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