Proof of Labelled enumeration theorem

Proof

It follows from the re-labelling construction that there are

$$\frac{1}{|G|} \sum_{r_1 + r_2 + \cdots + 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!}{|G|} \sum_{r_1 + r_2 + \cdots + r_n = k} [z^{r_1}] g(z) [z^{r_2}] g(z) \cdots [z^{r_n}] g(z) \; = \; \frac{k!}{|G|} [z^k] g(z)^n$$

different configurations of total size k. The formula evaluates to an integer because $[z^k] g(z)^n$ is zero for k < n (remember that g does not include objects of size zero) and when $k \ge n$ we have $n!|k!$ and the order $|G|$ of G divides the order of $S_n$, which is $n!$, by Lagrange's theorem. The conclusion is that the EGF of the labelled configurations is given by

$$f_n(z) = \sum_{k \ge 0} \left( \frac{k!}{|G|} [z^k] g(z)^n \right) \frac{z^k}{k!} = \frac{1}{|G|} \sum_{k \ge 0} z^k [z^k] g(z)^n = \frac{g(z)^n}{|G|}.$$

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|.$