Pólya enumeration theorem

Remarks

Proof idea: by Burnside's lemma, the number of orbits is the average number of colourings fixed by an element $g$. A colouring is fixed by $g$ exactly when it is constant on each cycle of $g$, so $g$ fixes $m^{c_1(g) + \cdots + c_d(g)}$ colourings. The weighted form follows from a weighted Burnside lemma in the same way, since a cycle of length $j$ with colour $c$ contributes $c^j$.

Example: colour the $4$ beads of a necklace black or white, up to rotation. The rotation group $C_4$ has cycle index $\frac{1}{4}(t_1^4 + t_2^2 + 2 t_4)$. With $m = 2$ this gives $\frac{1}{4}(16 + 4 + 4) = 6$ necklaces. With colours $b$ and $w$, the weighted form gives $b^4 + b^3 w + 2 b^2 w^2 + b w^3 + w^4$, so $2$ of the necklaces have two beads of each colour.

The group acts on the positions $X$, not on the colours. If one also allows permutations of the colours, the count changes, and the theorem has to be replaced by a version for the product group.

Going deeper

For a student

The theorem refines Burnside's lemma by keeping track of how many times each colour is used. It counts unlabelled structures, such as isomorphism classes of graphs or chemical isomers, by letting the symmetric group act on positions. In the symbolic method, the multiset and cycle constructions for unlabelled classes are instances of the same idea. The cycle index of the symmetric group $S_d$ acting on $d$ points is $\sum_{\lambda} p_\lambda / z_\lambda$, a sum over the partitions $\lambda$ of $d$. Here $p_\lambda = \prod_j t_j^{m_j}$ and $z_\lambda = \prod_j j^{m_j} m_j!$, where $m_j$ is the number of parts of $\lambda$ equal to $j$. With $t_j$ read as power sums, this links the theorem to symmetric functions.