Exponential formula

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Statement[edit]

For any formal power series of the form

f(x)=a_1 x+{a_2 \over 2}x^2+{a_3 \over 6}x^3+\cdots+{a_n \over n!}x^n+\cdots\,

we have

\exp f(x)=e^{f(x)}=\sum_{n=0}^\infty {b_n \over n!}x^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 π runs through the list of all partitions { S1, ..., Sk } of the set { 1, ..., n }. (When k = 0, the product is empty and by definition equals 1.)

One can write the 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 \over n!} x^n \right) = \sum_{n=0}^\infty {B_n(a_1,\dots,a_n) \over n!} x^n,

where Bn(a1, ..., an) is the nth complete Bell polynomial.

Examples[edit]

  • 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.
  • If bn = 2n(n−1)/2 is the number of graphs whose vertices are a given n-point set, then an 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 bn counts graphs without cycles, then an counts trees (connected grphs without cycles).
  • If bn counts directed graphs whose edges (rather than vertices) are a given n point set, then an counts connected directed graphs with this edge set.

Applications[edit]

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 (possibly disconnected) 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(Z) can be written as a sum over connected Feynman diagrams, in terms of connected correlation functions.

References[edit]