exponential formula

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\; \backslash over\; 2\}x^2+\{a\_3\; \backslash over\; 6\}x^3+\backslash cdots+\{a\_n\; \backslash over\; n!\}x^n+\backslash cdots\backslash ,$$

we have

$$\backslash exp\; f(x)=e^\{f(x)\}=\backslash sum\_\{n=0\}^\backslash infty\; \{b\_n\; \backslash over\; n!\}x^n,\backslash ,$$

where

$$b\_n\; =\; \backslash sum\_\{\backslash pi=\backslash left\backslash \{\backslash ,S\_1,\backslash ,\backslash dots,\backslash ,S\_k\backslash ,\backslash right\backslash \}\}\; a\_\{\backslash left|S\_1\backslash right|\}\backslash cdots\; a\_\{\backslash left|S\_k\backslash right|\},$$

and the index $\backslash pi$ runs through all partitions $\backslash \{\; S\_1,\backslash ldots,S\_k\; \backslash \}$ of the set

$\backslash \{\; 1,\backslash ldots,\; n\; \backslash \}$. (When $k\; =\; 0,$ the product is empty and by definition equals $1$.)

One can write the formula in the following form:

$$b\_n\; =\; B\_n(a\_1,a\_2,\backslash dots,a\_n),$$

and thus

$$\backslash exp\backslash left(\backslash sum\_\{n=1\}^\backslash infty\; \{a\_n\; \backslash over\; n!\}\; x^n\; \backslash right)\; =\; \backslash sum\_\{n=0\}^\backslash infty\; \{B\_n(a\_1,\backslash dots,a\_n)\; \backslash over\; n!\}\; x^n,$$

where $B\_n(a\_1,\backslash ldots,a\_n)$ 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:$$\backslash exp\backslash left(\backslash sum\_\{n=1\}^\backslash infty\; a\_n\; \{x^n\; \backslash over\; n\}\; \backslash right)\; =\; \backslash sum\_\{n=0\}^\backslash infty\; Z\_n(a\_1,\backslash dots,a\_n)\; x^n,$$where $Z\_n$ stands for the cycle index polynomial for the symmetric group $S\_n$, defined as:$$Z\_n\; (x\_1,\backslash cdots\; ,x\_n)\; =\; \backslash frac\; 1\{n!\}\; \backslash sum\_\{\backslash sigma\backslash in\; S\_n\}\; x\_1^\{\backslash sigma\_1\}\backslash cdots\; x\_n^\{\backslash sigma\_n\}$$and $\backslash sigma\_j$ denotes the number of cycles of $\backslash sigma$ of size $j\backslash in\; \backslash \{\; 1,\; \backslash cdots,\; n\; \backslash \}$. This is a consequence of the general relation between $Z\_n$ and Bell polynomials:$$Z\_n(x\_1,\backslash dots,x\_n)\; =\; \{1\; \backslash over\; n!\}\; B\_n(0!\backslash ,x\_1,\; 1!\backslash ,x\_2,\; \backslash dots,\; (n-1)!\backslash ,x\_n).$$

In combinatorial applications, the numbers $a\_n$ 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.

• $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 $\backslash \{1,2,3\backslash \}$ that has a single block of size $3$, there are three partitions of $\backslash \{1,2,3\backslash \}$ that split it into a block of size $2$ and a block of size $1$, and there is one partition of $\backslash \{1,2,3\backslash \}$ that splits it into three blocks of size $1$. This also follows from $Z\_3\; (a\_1,a\_2,a\_3)\; =\; \{1\; \backslash over\; 6\}(2\; a\_3\; +\; 3\; a\_1\; a\_2\; +\; a\_1^3)\; =\; \{1\; \backslash over\; 6\}\; B\_3\; (a\_1,\; a\_2,\; 2\; a\_3)$, since one can write the group $S\_3$ as $S\_3\; =\; \backslash \{\; (1)(2)(3),\; (1)(23),\; (2)(13),\; (3)(12),\; (123),\; (132)\; \backslash \}$, using cyclic notation for permutations.
• 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 graphs without cycles).
• If $b\_n$ counts directed graphs whose {{em|edges}} (rather than vertices) are a given $n$ point set, then $a\_n$ counts connected directed graphs with this edge set.
• In quantum field theory and statistical mechanics, the partition functions $Z$, or more generally correlation functions, are given by a formal sum over Feynman diagrams. The exponential formula shows that $\backslash ln(Z)$ can be written as a sum over connected Feynman diagrams, in terms of connected correlation functions.

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

• {{Citation | authorlink=Richard P. Stanley | last1=Stanley | first1=Richard P. | title=Enumerative combinatorics. Vol. 2 | url=http://www-math.mit.edu/~rstan/ec/ | publisher=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