Fundamental theorem of combinatorial enumeration

From Wikipedia, the free encyclopedia

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.

Contents

[edit] 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}{|G|}.

We are able to enumerate filled slot configurations using either PET in the unlabelled case or the labelled enumeration theorem in the labelled case. We now ask about the generating function of configurations obtained when there is more than one set of slots, with a permutation group acting on each. Clearly the orbits do not intersect and we may add the respective generating functions. Suppose, for example, that we want to enumerate unlabelled sequences of length two or three of some objects contained in a set X. There are two sets of slots, the first one containing two slots, and the second one, three slots. The group acting on the first set is E2, and on the second slot, E3. We represent this by the following formal power series in X:

X^2/E_2 \; + \; X^3/E_3

where the term Xn / G is used to denote the set of orbits under G and X^n = X \times \ldots \times X, which denotes in the obvious way the process of distributing the objects from X with repetition into the n slots. Similarly, consider the labelled problem of creating cycles of arbitrary length from a set of labelled objects X. This yields the following series of actions of cyclic groups:

X/C_1 \; + \; X^2/C_2 \; + \; X^3/C_3 \; + \; X^4/C_4 \; + \cdots.

Clearly we can assign meaning to any such power series of quotients (orbits) with respect to permutation groups, where we restrict the groups of degree n to the conjugacy classes \operatorname{Conj}(S_n) of the symmetric group Sn, which form a unique factorization domain. (The orbits with respect to two groups from the same conjugacy class are isomorphic.) This motivates the following definition.

A class \mathcal{C}\in \mathbb{N}[\mathfrak{A}] of combinatorial structures is a formal series

\mathcal{C} = \sum_{n \ge 1} \sum_{G\in \operatorname{Conj}(S_n)} c_G (X^n/G)

where \mathfrak{A} (the "A" is for "atoms") is the set of primes of the UFD \{\operatorname{Conj}(S_n)\}_{n\ge 1} and c_G \in \mathbb{N}.

In the following we will simplify our notation a bit and write e.g.

E_2 + E_3 \mbox{ and } C_1 + C_2 + C_3 + \cdots.

for the classes mentioned above.

[edit] The fundamental theorem of combinatorial enumeration

Let \mathcal{C}\in\mathbb{N}[\mathfrak{A}] be a class of combinatorial structures. The OGF F(z) of \mathcal{C}(X) where X has OGF f(z) and the EGF G(z) of \mathcal{C}(X) where X is labelled with EGF g(z) are given by

F(z) = \sum_{n \ge 1} \sum_{G\in \operatorname{Conj}(S_n)} c_G Z(G)(f(z), f(z^2), \ldots f(z^n))

and

G(z) = \sum_{n \ge 1} \left(\sum_{G\in \operatorname{Conj}(S_n)} \frac{c_G}{|G|}\right) g(z)^n.

In the labelled case we have the additional requirement that X not contain elements of size zero. It will sometimes prove convenient to add one to G(z) to indicate the presence of one copy of the empty set. It is possible to assign meaning to both \mathcal{C}\in\mathbb{Z}[\mathfrak{A}] (the most common example is the case of unlabelled sets) and \mathcal{C}\in\mathbb{Q}[\mathfrak{A}]. To prove the theorem simply apply PET (Pólya enumeration theorem) and the labelled enumeration theorem.

The power of this theorem lies in the fact that it makes it possible to construct operators on generating functions that represent combinatorial classes. A structural equation between combinatorial classes thus translates directly into an equation in the corresponding generating functions. Moreover in the labelled case it is evident from the formula that we may replace g(z) by the atom z and compute the resulting operator, which may then be applied to EGFs. We now proceed to construct the most important operators. The reader may wish to compare with the data on the cycle index page.

[edit] The sequence operator \mathfrak{S}

This operator corresponds to the class

1 + E_1 + E_2 + E_3 + \cdots\,

and represents sequences, i.e. the slots are not being permuted and there is exactly one empty sequence. We have

F(z) = 1 + \sum_{n\ge 1} Z(E_n)(f(z), f(z^2), \ldots f(z^n)) = 1 + \sum_{n\ge 1} f(z)^n = \frac{1}{1-f(z)}

and

G(z) = 1 + \sum_{n\ge 1} \left(\frac{1}{|E_n|}\right) g(z)^n = \frac{1}{1-g(z)}.

[edit] 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_{n\ge 1} Z(C_n)(f(z), f(z^2), \ldots f(z^n)) = \sum_{n\ge 1} \frac{1}{n} \sum_{d|n} \varphi(d) f(z^d)^{n/d}

or

F(z) = \sum_{k\ge 1} \varphi(k) \sum_{m\ge 1} \frac{1}{km} f(z^k)^m = \sum_{k\ge 1} \frac{\varphi(k)}{k} \log \frac{1}{1-f(z^k)}

and

G(z) = \sum_{n\ge 1} \left(\frac{1}{|C_n|}\right) g(z)^n = \log \frac{1}{1-g(z)}.

This operator, together with the set operator \mathfrak{P}, and their restrictions to specific degrees are used to compute random permutation statistics. There are two useful restrictions of this operator, namely to even and odd cycles.

The labelled even cycle operator \mathfrak{C}_\operatorname{even} is

C_2 + C_4 + C_6 + \cdots\,

which yields

G(z) = \sum_{n\ge 1} \left(\frac{1}{|C_{2n}|}\right) g(z)^{2n} = \frac{1}{2} \log \frac{1}{1-g(z)^2}.

This implies that the labelled odd cycle operator \mathfrak{C}_\operatorname{odd}

C_1 + C_3 + C_5 + \cdots

is given by

G(z) = \log \frac{1}{1-g(z)} - \frac{1}{2} \log \frac{1}{1-g(z)^2} = \frac{1}{2} \log \frac{1+g(z)}{1-g(z)}.

[edit] The dihedral operator \mathfrak{D}

The series for this operator is

D_1 + D_2 + D_3 + \cdots\,

i.e. these are cycles that may be "flipped over" i.e. reflected. Using the cycle index we have

F(z) = \sum_{n\ge 1} Z(D_n)(f(z), f(z^2), \ldots f(z^n))

or

\frac{1}{2} \mathfrak{C}(f(z)) + \frac{1}{2} \sum_{m\ge 0} f(z) f(z^2)^m + \frac{1}{4} \sum_{m\ge 1} \left( f(z)^2 f(z^2)^{m-1} + f(z^2)^m \right)

which yields

\frac{1}{2} \mathfrak{C}(f(z)) + \frac{1}{4} \frac{2 f(z) + f(z)^2 + f(z^2)}{1 - f(z^2)}.

For the labelled case we have

G(z) = \sum_{n\ge 1} \left(\frac{1}{|D_n|}\right) g(z)^n = \frac{1}{2} \log \frac{1}{1-g(z)}.

[edit] 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_{n\ge 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_{n\ge 1} \sum_{l=1}^n f(z^l) y^{n-1} [y^{n-l}] M(f(z), y)

which is

\sum_{l\ge 1} f(z^l) y^{l-1} \sum_{n\ge 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_{l\ge 1} f(z^l) y^{l-1}\right) M(f(z), y).

This immediately implies by logarithmic differentiation that

\frac{\partial}{\partial y} \log M(f(z), y) = \sum_{l\ge 1} f(z^l) y^{l-1}.

Integrating we have

\log M(f(z), y) = \sum_{l\ge 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_{l\ge 1} \frac{f(z^l)}{l} \right).

For the labelled case we have

G(z) = 1 + \sum_{n\ge 1} \left(\frac{1}{|S_n|}\right) g(z)^n = \sum_{n\ge 0} \frac{g(z)^n}{n!} = \exp g(z).

In the labelled case we denote the operator by \mathfrak{P}, and in the unlabelled case, by \mathfrak{M}.

Two useful restructions of the labelled set operator are to sets containing an even and an odd number of elements. The operator \mathfrak{P}_\operatorname{even} has the series

1 + S_2 + S_4 + S_6 + \cdots\,

and hence

G(z) = 1 + \sum_{n\ge 1} \left(\frac{1}{|S_{2n}|}\right) g(z)^{2n} = \sum_{n\ge 0} \frac{g(z)^{2n}}{(2n)!} = \cosh g(z).

Similarly, the operator \mathfrak{P}_\operatorname{odd} has the series

S_1 + S_3 + S_5 + S_7 + \cdots\,

and hence

G(z) = \sum_{n\ge 1} \left(\frac{1}{|S_{2n-1}|}\right) g(z)^{2n-1} = \sum_{n\ge 1} \frac{g(z)^{2n-1}}{(2n-1)!} = \sinh g(z).

[edit] External links

[edit] 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).