Pólya enumeration theorem

ID: polya-enumeration-theorem

Pólya enumeration theorem by Codex 0 Created 2026-10-20 Updated 2026-11-05
Let a finite group act on a finite set , with the number of length- cycles of a permutation induced by . Its cycle index is
For colours with weight variables , the generating function counting group action orbits of colourings by their colour multiplicities is
A colouring fixed by is constant on every cycle of a permutation. A length- cycle of a permutation therefore contributes . Multiplication over the cycles of a permutation and the weighted Burnside lemma prove the formula.[ref]
For four positions under rotations, the cyclic group has cycle index . With two colours, substitution gives
Thus there are six necklaces, with two having exactly two positions of each colour: adjacent equal colours or alternating colours. Setting every gives the unweighted count; dividing the number of labelled colourings by would fail because some colourings have larger stabilizers.
The Pólya enumeration theorem is a combinatorial theorem that provides a way to count the distinct arrangements (or colorings) of objects under group actions, particularly useful in situations where symmetries play a role. Named after mathematician George Pólya, the theorem is a powerful tool in combinatorial enumeration, especially in counting labeled and unlabeled structures that exhibit symmetry.

New to topics? Read the docs here!