Pólya enumeration theorem (source code)

= Pólya enumeration theorem
{c}
{title2=$Z_G(z_j\gets\sum_a x_a^j)$}

Let a finite <group> $G$ act on a finite <set> $X$, with $c_j(g)$ the number of length-$j$ <cycles of a permutation> induced by $g$. Its <cycle index> is
$$
Z_G(z_1,\ldots,z_{|X|})=\frac1{|G|}\sum_{g\in G}\prod_jz_j^{c_j(g)}.
$$
For $q$ colours with weight <variables> $x_1,\ldots,x_q$, the <generating function> counting <group action> <orbits> of colourings by their colour multiplicities is
$$
Z_G\left(\sum_ax_a,\sum_ax_a^2,\sum_ax_a^3,\ldots\right).
$$
A colouring fixed by $g$ is constant on every <cycle of a permutation>. A length-$j$ <cycle of a permutation> therefore contributes $\sum_a x_a^j$. Multiplication over the <cycles of a permutation> and the <weighted Burnside lemma> prove the formula.<Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen by George Pólya>[ChapterI, §16, printed page163]{ref}

For four positions under <rotations>, the <cyclic group> has <cycle index> $(z_1^4+z_2^2+2z_4)/4$. With two colours, substitution gives
$$
x^4+x^3y+2x^2y^2+xy^3+y^4.
$$
Thus there are six <necklaces>, with two having exactly two positions of each colour: adjacent equal colours or alternating colours. Setting every $x_a=1$ gives the unweighted count; dividing the number of labelled colourings by $|G|$ would fail because some colourings have larger <stabilizers>.