Labelled enumeration theorem

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 $f\_n(z)$ of the number of different configurations under this re-labelling process is given by

:$f\_n(z)\; =\; frac\{g(z)^n\}sum\_\{r\_1\; +\; r\_2\; +\; ldots\; +\; r\_n\; =\; k\}\{k\; choose\; r\_1,\; r\_2,\; ldots\; r\_n\}\; ;r\_1!\; [z^\{r\_1\}]\; g(z)\; ;r\_2!\; [z^\{r\_2\}]\; g(z)\; ;cdots\; ;r\_n!\; [z^\{r\_n\}]\; g(z)$

or

:$frac\{k!\}\; [z^k]\; g(z)^n\; ight)\; frac\{z^k\}\{k!\}\; =frac\{1\}\; sum\_\{k\; ge\; 0\}\; z^k\; [z^k]\; g(z)^n\; =\; frac\{g(z)^n\}.$

This formula could also be obtained by enumerating sequences, i.e. the case when the slots are not being permuted, and by using the above argument without the $1/|G|$-factor to show that their generating function under re-labelling is given by $g(z)^n$. Finally note that every sequence belongs to an orbit of size $|G|$, hence the generating function of the orbits is given by $g(z)^n/|G|.$