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.
Articles by others on the same topic
Let a finite group act on a finite set , with the number of length- cycles of a permutation induced by . Its cycle index isFor colours with weight variables , the generating function counting group action orbits of colourings by their colour multiplicities isA 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]
Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen by George Pólya. ChapterI, §16, printed page163
For four positions under rotations, the cyclic group has cycle index . With two colours, substitution givesThus 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.