Exponential formula

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.

1 Definition
2 Examples
3 Applications in physics
4 Bell polynomials
5 References

Definition

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\{\,B_1,\,\dots,\,B_k\,\right\}} a_{\left|B_1\right|}\cdots a_{\left|B_k\right|},$

and the index π runs through the list of all partitions { B₁, ..., B_k } of the set { 1, ..., n }. (When k = 0, the product over 0 elements is by definition equal to 1.)

In applications, the numbers a_n often count the number of some sort of "connected" structure on an n-point set, and the numbers b_n count the number of (possibly disconnected) structures. The numbers b_n/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 a_n/n! count isomorphism classes of connected structures in the same way.

For example,

$b_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. This polynomial in the three variables a₁, a₂, a₃ is a Bell polynomial.

Essentially, the exponential formula is a power-series version of a special case of Faà di Bruno's formula.

Examples

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

Applications in physics

In quantum field theory and statistical mechanics, the partition functions Z, or more generally correlation functions, are give by a formal sum over Feynman diagrams. The exponential formula shows that log(Z) can be given as a sum over connected Feynman diagrams, in terms of connected correlation functions.

Bell polynomials

One can write the formula in the following form, where B_n(a₁, ..., a_n) is the nth complete Bell polynomial:

$\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.$

References

Stanley, Richard P. (1999), Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, MR 1676282, ISBN 978-0-521-56069-6; 978-0-521-78987-5, http://www-math.mit.edu/~rstan/ec/ Chapter 5

Open source encyclopedia content modification information:

This page was last modified on 30 August 2009 at 13:59.

Authorship and Review

Open source encyclopedia content provided here is not reviewed directly by MedLibrary.org. Content is sourced directly from Wikipedia and is authored by an open community of volunteers. It is not produced by or in any way affiliated with MedLibrary.org.

Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Exponential formula", which is available in its original form here:

http://en.wikipedia.org/w/index.php?title=Exponential_formula

All material adapted used from Wikipedia is available under the terms of the GNU Free Documentation License. Wikipedia® itself is a registered trademark of the Wikimedia Foundation, Inc.

Exponential formula -- Please Click to Return to Front Page