Labelled enumeration theorem

In combinatorial mathematics, the labelled enumeration theorem is the counterpart of the Pólya enumeration theorem for the labelled case, where we have a set of labelled objects given by an exponential generating function (EGF) g(z) which are being distributed into n slots and a permutation group G which permutes the slots, thus creating equivalence classes of configurations. There is a special re-labelling operation that re-labels the objects in the slots, assigning labels from 1 to k, where k is the total number of nodes, i.e. the sum of the number of nodes of the individual objects. The EGF ${\displaystyle f_{n}(z)}$ of the number of different configurations under this re-labelling process is given by

In particular, if G is the symmetric group of order n (hence, |G| = n!), the functions f_n(z) can be further combined into a single generating function:

which is exponential w.r.t. the variable z and ordinary w.r.t. the variable t.

We assume that an object ${\displaystyle \omega }$ of size ${\displaystyle |\omega |}$ represented by ${\displaystyle z^{|\omega |}/|\omega |!}$ contains ${\displaystyle |\omega |=m\,}$ labelled internal nodes, with the labels going from 1 to m. The action of G on the slots is greatly simplified compared to the unlabelled case, because the labels distinguish the objects in the slots, and the orbits under G all have the same size ${\displaystyle |G|}$. (The EGF g(z) may not include objects of size zero. This is because they are not distinguished by labels and therefore the presence of two or more of such objects creates orbits whose size is less than ${\displaystyle |G|}$.) As mentioned, the nodes of the objects are re-labelled when they are distributed into the slots. Say an object of size ${\displaystyle r_{1}}$ goes into the first slot, an object of size ${\displaystyle r_{2}}$ into the second slot, and so on, and the total size of the configuration is k, so that

...
Wikipedia