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 formwe havewhereand the index
runs through all
partitions
of the set
. (When
the product is
empty and by definition equals
.)
Formula in other expressions
One can write the formula in the following form:and thuswhere
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
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
b3=B3(a1,a2,a3)=a3+3a2a1+
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
Z3(a1,a2,a3)={1\over6}(2a3+3a1a2+
={1\over6}B3(a1,a2,2a3)
, since one can write the
group
as
S3=\{(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)\}
, using cyclic notation for
permutations.
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).
counts
directed graphs whose (rather than vertices) are a given
point set, then
counts connected directed graphs with this edge set.
, 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.
References