Exponential formula explained

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 formf(x)=a_1 x+x^2+x^3+\cdots+x^n+\cdots\,we have\exp f(x)=e^=\sum_^\infty x^n,\,whereb_n = \sum_ a_\cdots a_,and the index

\pi

runs through all partitions

\{S1,\ldots,Sk\}

of the set

\{1,\ldots,n\}

. (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:b_n = B_n(a_1,a_2,\dots,a_n),and thus\exp\left(\sum_^\infty x^n \right) = \sum_^\infty x^n,where

Bn(a1,\ldots,an)

is the

n

th complete Bell polynomial.

Alternatively, the exponential formula can also be written using the cycle index of the symmetric group, as follows:\exp\left(\sum_^\infty a_n \right) = \sum_^\infty Z_n(a_1,\dots,a_n) x^n,where

Zn

stands for the cycle index polynomial for the symmetric group

Sn

, defined as:Z_n (x_1,\cdots,x_n) = \frac 1 \sum_ x_1^\cdots x_n^and

\sigmaj

denotes the number of cycles of

\sigma

of size

j\in\{1,,n\}

. This is a consequence of the general relation between

Zn

and Bell polynomials:Z_n(x_1,\dots,x_n) = B_n(0!\,x_1, 1!\,x_2, \dots, (n-1)!\,x_n).

Combinatorial interpretation

In combinatorial applications, the numbers

an

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.

Examples

b3=B3(a1,a2,a3)=a3+3a2a1+

3,
a
1
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

. This also follows from

Z3(a1,a2,a3)={1\over6}(2a3+3a1a2+

3)
a
1

={1\over6}B3(a1,a2,2a3)

, since one can write the group

S3

as

S3=\{(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)\}

, using cyclic notation for permutations.

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.

bn

counts graphs without cycles, then

an

counts trees (connected graphs without cycles).

bn

counts directed graphs whose (rather than vertices) are a given

n

point set, then

an

counts connected directed graphs with this edge set.

Z

, or more generally correlation functions, are given by a formal sum over Feynman diagrams. The exponential formula shows that

ln(Z)

can be written as a sum over connected Feynman diagrams, in terms of connected correlation functions.

References