# Exponential formula

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Exponential_formula
> Markdown URL: https://mediated.wiki/source/Exponential_formula.md
> Source: https://en.wikipedia.org/wiki/Exponential_formula
> Source revision: 1352557308
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [combinatorial](/source/combinatorics) [mathematics](/source/mathematics), the '''exponential formula''' (called the '''polymer expansion''' in [physics](/source/physics)) states that the [exponential generating function](/source/exponential_generating_function) for structures on [finite set](/source/finite_set)s is the [exponential](/source/exponential_function) of the exponential generating function for connected structures.
The exponential formula is a [power series](/source/power_series) version of a special case of [Faà di Bruno's formula](/source/Fa%C3%A0_di_Bruno's_formula).

==Algebraic statement==
Here is a purely [algebra](/source/algebra)ic statement, as a first introduction to the combinatorial use of the formula.

For any [formal power series](/source/formal_power_series) of the form
: <math>f(x) = a_1 x + a_2 \frac{x^2}{2} + a_3 \frac{x^3}{6} + \dots + a_n \frac{x^n}{n!} + \dots</math>
we have
: <math>\exp f(x) = e^{f(x)} = \sum_{n=0}^\infty b_n \frac{x^n}{n!}</math>
where
: <math>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 [partitions](/source/partition_of_a_set) <math>\{ S_1, \ldots, S_k \}</math> of the set <math>\{ 1,\ldots, n \}</math>. (When <math>k = 0</math>, the product is [empty](/source/empty_product) and by definition equals <math>1</math>.)

===Other expressions===
* One can write the exponential formula in the following form
:: <math>b_n = B_n(a_1, a_2, \dots, a_n)</math>
: and thus
:: <math>\exp\left( \sum_{n=1}^\infty a_n \frac{x^n}{n!} \right) = \sum_{n=0}^\infty B_n(a_1,\dots,a_n) \frac{x^n}{n!}</math>
: where <math>B_n(a_1, \ldots, a_n)</math> is the <math>n</math>{{Sup|th}} complete [Bell polynomial](/source/Bell_polynomial).

* The exponential formula can also be written as follows:
:: <math>\exp\left( \sum_{n=1}^\infty a_n \frac{x^n}{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](/source/cycle_index) polynomial for the [symmetric group](/source/symmetric_group) <math>S_n</math>, defined as:
:: <math>Z_n(a_1, \dots, a_n) = \frac{1}{n!} \sum_{\sigma\in S_n} a_1^{\sigma_1} \cdots a_n^{\sigma_n}</math>
: and <math>\sigma_j</math> denotes the number of cycles of <math>\sigma</math> of size <math>j \in \{1, \dots, n\}</math>. This is a consequence of the general relation between <math>Z_n</math> and Bell polynomials:
:: <math>n! Z_n(a_1, \dots, a_n) = B_n(0!\,a_1, 1!\,a_2, \dots, (n-1)!\,a_n).</math>

==Combinatorial interpretation==

In combinatorial 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 (see [combinatorial species](/source/combinatorial_species)). The numbers <math>b_n/n!</math> count the number of [isomorphism class](/source/isomorphism_class)es of structures on <math>n</math> points, with each structure being weighted by the reciprocal of its [automorphism group](/source/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](/source/group_(mathematics)) <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](/source/permutation)s.
* If <math>b_n = 2^{n(n-1)/2}</math> is the number of [graphs](/source/graph_(discrete_mathematics)) whose vertices are a given <math>n</math>-point set, then <math>a_n</math> is the number of [connected graphs](/source/connectivity_(graph_theory)) 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 [trees](/source/tree_(graph_theory)) (connected graphs without cycles).
* If <math>b_n</math> counts [directed graph](/source/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 [quantum field theory](/source/quantum_field_theory) and [statistical mechanics](/source/statistical_mechanics), the [partition functions](/source/Partition_function_(mathematics)) <math>Z</math>, or more generally [correlation function](/source/correlation_function)s, are given by a formal sum over [Feynman diagram](/source/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 function](/source/connected_correlation_function)s.

==See also==

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

==References==

* {{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](/source/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

---
Adapted from the Wikipedia article [Exponential formula](https://en.wikipedia.org/wiki/Exponential_formula) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Exponential_formula?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.