Fundamental theorem of combinatorial enumeration

The fundamental theorem of combinatorial enumeration is a theorem in combinatorics that solves the enumeration problem of labelled and unlabelled combinatorial classes. The unlabelled case is based on the Pólya enumeration theorem.This theorem is also known as the "folklore theorem of enumeration" and its most important application is the creation of symbolic operators, the so-called "symbolic method", that makes it possible to translate equations involving combinatorial structures directly (and automatically) into equations in the generating functions of these structures. For an introduction to the symbolic method, consult the page on symbolic combinatorics.

Classes of combinatorial structures

Consider the problem of distributing objects given by a generating function into a set of "n" slots, where a permutation group "G" of degree "n" acts on the slots to create an equivalence relation of filled slot configurations, and asking about the generating function of the configurations by weight of the configurations with respect to this equivalence relation, where the weight of a configuration is the sum of the weights of the objects in the slots. We will first explain how to solve this problem in the labelled and the unlabelled case and use the solution to motivate the creation of classes of combinatorial structures.

The Pólya enumeration theorem solves this problem in the unlabelled case. Let "f"("z") be the ordinary generating function (OGF) of the objects, then the OGF of the configurations is given by the substituted cycle index

:$Z(G)(f(z),\; f(z^2),\; ldots,\; f(z^n)).,$

In the labelled case we use an exponential generating function (EGF) "g"("z") of the objects and apply the Labelled enumeration theorem, which says that the EGF of the configurations is given by

:$frac\{g(z)^n\}\; ight)\; g(z)^n\; =\; frac\{1\}\{1-g(z)\}.$

The cycle operator $mathfrak\{C\}$

This operator corresponds to the class

:$C\_1\; +\; C\_2\; +\; C\_3\; +\; cdots,$

i.e. cycles containing at least one object. We have

:$F(z)\; =\; sum\_\{nge\; 1\}\; Z(C\_n)(f(z),\; f(z^2),\; ldots\; f(z^n))\; =sum\_\{nge\; 1\}\; frac\{1\}\{n\}\; sum\_\{d|n\}\; varphi(d)\; f(z^d)^\{n/d\}$

or

:$F(z)\; =\; sum\_\{kge\; 1\}\; varphi(k)\; sum\_\{mge\; 1\}\; frac\{1\}\{km\}\; f(z^k)^m\; =sum\_\{kge\; 1\}\; frac\{varphi(k)\}\{k\}\; log\; frac\{1\}\{1-f(z^k)\}$

and

:$G(z)\; =\; sum\_\{nge\; 1\}\; left(frac\{1\}\; ight)\; g(z)^n\; =\; frac\{1\}\{2\}\; log\; frac\{1\}\{1-g(z)\}.$

The multiset/set operator $mathfrak\{M\}/mathfrak\{P\}$

The series is

:$1\; +\; S\_1\; +\; S\_2\; +\; S\_3\; +\; cdots,$

i.e. the symmetric group is applied to the slots.This creates multisets in the unlabelled case and sets in the labelled case(there are no multisets in the labelled case because the labels distinguish multiple instances of the same object from the set being put into different slots).We include the empty set in both the labelled and the unlabelled case.

Again do the unlabelled case first. Introduce the function

:$M(f(z),\; y)\; =\; sum\_\{nge\; 0\}\; y^n\; Z(S\_n)(f(z),\; f(z^2),\; ldots\; f(z^n))$

so that

:$mathfrak\{M\}(f(z))\; =\; M(f(z),\; 1).,$

Recall the recurrence relation

:$Z(S\_n)\; =\; frac\{1\}\{n\}\; sum\_\{l=1\}^n\; a\_l\; ;\; Z(S\_\{n-l\})$

which shows that

:$frac\{partial\}\{partial\; y\}\; M(f(z),\; y)\; =sum\_\{nge\; 1\}\; sum\_\{l=1\}^n\; f(z^l)\; y^\{n-1\}\; [y^\{n-l\}]\; M(f(z),\; y)$

which is

:$sum\_\{lge\; 1\}\; f(z^l)\; y^\{l-1\}\; sum\_\{nge\; l\}\; y^\{n-l\}\; [y^\{n-l\}]\; M(f(z),\; y)$

which yields in turn

:$frac\{partial\}\{partial\; y\}\; M(f(z),\; y)\; =\; left(sum\_\{lge\; 1\}\; f(z^l)\; y^\{l-1\}\; ight)\; M(f(z),\; y).$

This immediately implies by logarithmic differentiation that:$frac\{partial\}\{partial\; y\}\; log\; M(f(z),\; y)\; =sum\_\{lge\; 1\}\; f(z^l)\; y^\{l-1\}.$

Integrating we have

:$log\; M(f(z),\; y)\; =\; sum\_\{lge\; 1\}\; frac\{f(z^l)\}\{l\}\; y^l$

because

:$log\; M(f(z),\; 0)\; =\; log\; Z(S\_0)\; =\; 0.,$

Evaluating $M(f(z),\; 1)$ we finally obtain

:$F(z)\; =\; exp\; left(\; sum\_\{lge\; 1\}\; frac\{f(z^l)\}\{l\}\; ight).$

For the labelled case we have

:$G(z)\; =\; 1\; +\; sum\_\{nge\; 1\}\; left(frac\{1\}\; ight)\; g(z)^\{2n-1\}\; =\; sum\_\{nge\; 1\}\; frac\{g(z)^\{2n-1\{(2n-1)!\}\; =\; sinh\; g(z).$

External links

*Marko Riedel, " [http://www.geocities.com/markoriedelde/papers/collier.pdf Pólya's enumeration theorem and the symbolic method.] "

*Philippe Flajolet and Robert Sedgewick, " [http://algo.inria.fr/flajolet/Publications/FlSe02.ps.gz Analytic combinatorics - Symbolic combinatorics.] "

References

* François Bergeron, Gilbert Labelle, Pierre Leroux, "Théorie des espèces et combinatoire des structures arborescentes", LaCIM, Montréal (1994). English version: "Combinatorial Species and Tree-like Structures", Cambridge University Press (1998).