View source for Exponential formula

In [[Combinatorics|combinatorial]] [[Mathematics|mathematics]], the '''exponential formula''' (called the '''polymer expansion''' in [[Physics:Physics|physics]]) states that the exponential generating function for structures on [[Finite set|finite set]]s is the [[Exponential function|exponential]] of the exponential generating function for connected structures.
The exponential formula is a [[Power series|power series]] version of a special case of [[Faà di Bruno's formula]].

==Algebraic statement==
Here is a purely [[Algebra|algebra]]ic statement, as a first introduction to the combinatorial use of the formula.

For any [[Formal power series|formal power series]] of the form
<math display="block">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\,</math>
we have
<math display="block">\exp f(x)=e^{f(x)}=\sum_{n=0}^\infty {b_n \over n!}x^n,\,</math>
where
<math display="block">b_n = \sum_{\pi=\left\{\,S_1,\,\dots,\,S_k\,\right\}} a_{\left|S_1\right|}\cdots a_{\left|S_k\right|},</math>
and the index <math>\pi</math> runs through all [[Partition of a set|partitions]] <math>\{ S_1,\ldots,S_k \}</math> of the set
<math>\{ 1,\ldots, n \}</math>. (When <math>k = 0,</math> the product is [[Empty product|empty]] and by definition equals <math>1</math>.)

===Formula in other expressions===
One can write the formula in the following form:
<math display="block">b_n = B_n(a_1,a_2,\dots,a_n),</math>
and thus
<math display="block">\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,</math>
where <math>B_n(a_1,\ldots,a_n)</math> is the <math>n</math>th complete Bell polynomial.

Alternatively, the exponential formula can also be written using the [[Cycle index|cycle index]] of the [[Symmetric group|symmetric group]], as follows:<math display="block">\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,</math>where <math>Z_n</math> stands for the cycle index polynomial for the symmetric group <math>S_n</math>, defined as:<math display="block">Z_n (x_1,\cdots ,x_n) = \frac 1{n!} \sum_{\sigma\in S_n} x_1^{\sigma_1}\cdots x_n^{\sigma_n}</math>and <math>\sigma_j</math> denotes the number of cycles of <math>\sigma</math> of size <math>j\in \{ 1, \cdots, n \}</math>. This is a consequence of the general relation between <math>Z_n</math> and [[Bell polynomials]]:<math display="block">Z_n(x_1,\dots,x_n) = {1 \over n!} B_n(0!\,x_1, 1!\,x_2, \dots, (n-1)!\,x_n).</math>

==The combinatorial formula==
In applications, the numbers <math>a_n</math> count the number of some sort of "connected" structure on an <math>n</math>-point set, and the numbers <math>b_n</math> count the number of (possibly disconnected) structures. The numbers <math>b_n/n!</math> count the number of [[Isomorphism class|isomorphism class]]es of structures on <math>n</math> points, with each structure being weighted by the reciprocal of its automorphism group, and the numbers <math>a_n/n!</math> count isomorphism classes of connected structures in the same way.

==Examples==
* <math>b_3 = B_3(a_1,a_2,a_3) = a_3 + 3a_2 a_1 + a_1^3,</math> because there is one partition of the set <math>\{1,2,3\}</math> that has a single block of size <math>3</math>, there are three partitions of <math>\{1,2,3\}</math> that split it into a block of size <math>2</math> and a block of size <math>1</math>, and there is one partition of <math>\{1,2,3\}</math> that splits it into three blocks of size <math>1</math>. This also follows from <math>Z_3 (a_1,a_2,a_3) = {1 \over 6}(2 a_3 + 3 a_1 a_2 + a_1^3) = {1 \over 6} B_3 (a_1, a_2, 2 a_3) </math>, since one can write the [[Group (mathematics)|group]] <math>S_3</math> as <math>S_3 = \{ (1)(2)(3), (1)(23), (2)(13), (3)(12), (123), (132) \}</math>, using cyclic notation for [[Permutation|permutation]]s.
* If <math>b_n = 2^{n(n-1)/2}</math> is the number of [[Graph (discrete mathematics)|graphs]] whose vertices are a given <math>n</math>-point set, then <math>a_n</math> is the number of [[Connectivity (graph theory)|connected graphs]] whose vertices are a given <math>n</math>-point set.
* There are numerous variations of the previous example where the graph has certain properties: for example, if <math>b_n</math> counts graphs without cycles, then <math>a_n</math> counts [[Tree (graph theory)|trees]] (connected graphs without cycles).
* If <math>b_n</math> counts [[Directed graph|directed graph]]s whose {{em|edges}} (rather than vertices) are a given <math>n</math> point set, then <math>a_n</math> counts connected directed graphs with this edge set.
*In [[Physics:Quantum field theory|quantum field theory]] and [[Physics:Statistical mechanics|statistical mechanics]], the [[Partition function (mathematics)|partition functions]] <math>Z</math>, or more generally [[Correlation function|correlation function]]s, are given by a formal sum over [[Physics:Feynman diagram|Feynman diagram]]s. The exponential formula shows that <math>\ln(Z)</math> can be written as a sum over connected Feynman diagrams, in terms of connected correlation functions.

==See also==

* {{annotated link|Surjection of Fréchet spaces}}

==References==

* {{Citation |  last1=Stanley | first1=Richard P. | title=Enumerative combinatorics. Vol. 2 | url=http://www-math.mit.edu/~rstan/ec/ | publisher={{wipe|Cambridge University Press}} | series=Cambridge Studies in Advanced Mathematics | isbn=978-0-521-56069-6 | id={{ISBN|978-0-521-78987-5}} | mr=1676282 | year=1999 | volume=62}} Chapter 5 page 3

[[Category:Exponentials]]
[[Category:Enumerative combinatorics]]

{{Sourceattribution|Exponential formula}}