From Wikipedia, the free encyclopedia
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
f
(
x
)
=
a
1
x
+
a
2
2
x
2
+
a
3
6
x
3
+
⋯
+
a
n
n
!
x
n
+
⋯
{\displaystyle 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
)
=
∑
n
=
0
∞
b
n
n
!
x
n
,
{\displaystyle \exp f(x)=e^{f(x)}=\sum _{n=0}^{\infty }{b_{n} \over n!}x^{n},\,}
where
b
n
=
∑
π
=
{
S
1
,
…
,
S
k
}
a
|
S
1
|
⋯
a
|
S
k
|
,
{\displaystyle 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
π
{\displaystyle \pi }
runs through all
partitions
{
S
1
,
…
,
S
k
}
{\displaystyle \{S_{1},\ldots ,S_{k}\}}
of the set
{
1
,
…
,
n
}
{\displaystyle \{1,\ldots ,n\}}
. (When
k
=
0
,
{\displaystyle k=0,}
the product is
empty and by definition equals
1
{\displaystyle 1}
.)
Formula in other expressions [ edit ]
One can write the formula in the following form:
b
n
=
B
n
(
a
1
,
a
2
,
…
,
a
n
)
,
{\displaystyle b_{n}=B_{n}(a_{1},a_{2},\dots ,a_{n}),}
and thus
exp
(
∑
n
=
1
∞
a
n
n
!
x
n
)
=
∑
n
=
0
∞
B
n
(
a
1
,
…
,
a
n
)
n
!
x
n
,
{\displaystyle \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
B
n
(
a
1
,
…
,
a
n
)
{\displaystyle B_{n}(a_{1},\ldots ,a_{n})}
is the
n
{\displaystyle n}
th complete
Bell polynomial .
Alternatively, the exponential formula can also be written using the cycle index of the symmetric group , as follows:
exp
(
∑
n
=
1
∞
a
n
x
n
n
)
=
∑
n
=
0
∞
Z
n
(
a
1
,
…
,
a
n
)
x
n
,
{\displaystyle \exp \left(\sum _{n=1}^{\infty }a_{n}{x^{n} \over n}\right)=\sum _{n=0}^{\infty }Z_{n}(a_{1},\dots ,a_{n})x^{n},}
where
Z
n
{\displaystyle Z_{n}}
stands for the cycle index polynomial for the symmetric group
S
n
{\displaystyle S_{n}}
, defined as:
Z
n
(
x
1
,
⋯
,
x
n
)
=
1
n
!
∑
σ
∈
S
n
x
1
σ
1
⋯
x
n
σ
n
{\displaystyle Z_{n}(x_{1},\cdots ,x_{n})={\frac {1}{n!}}\sum _{\sigma \in S_{n}}x_{1}^{\sigma _{1}}\cdots x_{n}^{\sigma _{n}}}
and
σ
j
{\displaystyle \sigma _{j}}
denotes the number of cycles of
σ
{\displaystyle \sigma }
of size
j
∈
{
1
,
⋯
,
n
}
{\displaystyle j\in \{1,\cdots ,n\}}
. This is a consequence of the general relation between
Z
n
{\displaystyle Z_{n}}
and
Bell polynomials :
Z
n
(
x
1
,
…
,
x
n
)
=
1
n
!
B
n
(
0
!
x
1
,
1
!
x
2
,
…
,
(
n
−
1
)
!
x
n
)
.
{\displaystyle Z_{n}(x_{1},\dots ,x_{n})={1 \over n!}B_{n}(0!\,x_{1},1!\,x_{2},\dots ,(n-1)!\,x_{n}).}
Combinatorial interpretation [ edit ]
In combinatorial applications, the numbers
a
n
{\displaystyle a_{n}}
count the number of some sort of "connected" structure on an
n
{\displaystyle n}
-point set, and the numbers
b
n
{\displaystyle b_{n}}
count the number of (possibly disconnected) structures. The numbers
b
n
/
n
!
{\displaystyle b_{n}/n!}
count the number of isomorphism classes of structures on
n
{\displaystyle n}
points, with each structure being weighted by the reciprocal of its automorphism group , and the numbers
a
n
/
n
!
{\displaystyle a_{n}/n!}
count isomorphism classes of connected structures in the same way.
Examples [ edit ]
b
3
=
B
3
(
a
1
,
a
2
,
a
3
)
=
a
3
+
3
a
2
a
1
+
a
1
3
,
{\displaystyle 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
}
{\displaystyle \{1,2,3\}}
that has a single block of size
3
{\displaystyle 3}
, there are three partitions of
{
1
,
2
,
3
}
{\displaystyle \{1,2,3\}}
that split it into a block of size
2
{\displaystyle 2}
and a block of size
1
{\displaystyle 1}
, and there is one partition of
{
1
,
2
,
3
}
{\displaystyle \{1,2,3\}}
that splits it into three blocks of size
1
{\displaystyle 1}
. This also follows from
Z
3
(
a
1
,
a
2
,
a
3
)
=
1
6
(
2
a
3
+
3
a
1
a
2
+
a
1
3
)
=
1
6
B
3
(
a
1
,
a
2
,
2
a
3
)
{\displaystyle Z_{3}(a_{1},a_{2},a_{3})={1 \over 6}(2a_{3}+3a_{1}a_{2}+a_{1}^{3})={1 \over 6}B_{3}(a_{1},a_{2},2a_{3})}
, since one can write the group
S
3
{\displaystyle S_{3}}
as
S
3
=
{
(
1
)
(
2
)
(
3
)
,
(
1
)
(
23
)
,
(
2
)
(
13
)
,
(
3
)
(
12
)
,
(
123
)
,
(
132
)
}
{\displaystyle S_{3}=\{(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)\}}
, using cyclic notation for permutations .
If
b
n
=
2
n
(
n
−
1
)
/
2
{\displaystyle b_{n}=2^{n(n-1)/2}}
is the number of graphs whose vertices are a given
n
{\displaystyle n}
-point set, then
a
n
{\displaystyle a_{n}}
is the number of connected graphs whose vertices are a given
n
{\displaystyle n}
-point set.
There are numerous variations of the previous example where the graph has certain properties: for example, if
b
n
{\displaystyle b_{n}}
counts graphs without cycles, then
a
n
{\displaystyle a_{n}}
counts trees (connected graphs without cycles).
If
b
n
{\displaystyle b_{n}}
counts directed graphs whose edges (rather than vertices) are a given
n
{\displaystyle n}
point set, then
a
n
{\displaystyle a_{n}}
counts connected directed graphs with this edge set.
In quantum field theory and statistical mechanics , the partition functions
Z
{\displaystyle Z}
, or more generally correlation functions , are given by a formal sum over Feynman diagrams . The exponential formula shows that
ln
(
Z
)
{\displaystyle \ln(Z)}
can be written as a sum over connected Feynman diagrams, in terms of connected correlation functions .
See also [ edit ]
References [ edit ]