Pólya enumeration theorem

The Pólya enumeration theorem counts configurations up to symmetry by combining a group action’s cycle structure with a generating function for allowed colors or states.

Cycle index: A polynomial that records the cycle lengths of permutations in a group action. It encodes the symmetry group’s cycle structure, the theorem’s central input.
Permutation group: A group whose elements are permutations of a set. The symmetries being counted form a permutation group on the configuration’s positions.
Necklace problem: The problem of counting circular bead arrangements up to rotations, and sometimes reflections. Rotations and reflections form the symmetries whose distinct bead colorings the theorem counts.
George Pólya: A Hungarian-American mathematician known for work in combinatorics, probability, and mathematical problem solving. He developed the enumeration method that bears his name.
Burnside's lemma: A counting theorem stating that the number of orbits equals the average number of fixed points of group elements. It counts unweighted orbits, while Pólya’s theorem also tracks color or state inventories.
Group action: A rule assigning each element of a group a permutation of a set while preserving the group operation. The theorem counts configurations by identifying those related through this action.
Fixed point (mathematics): An element left unchanged by a specified function or transformation. Burnside’s averaging step counts configurations fixed by each symmetry.
Graph coloring: An assignment of colors to a graph’s vertices subject to specified restrictions on adjacent vertices. Symmetry-aware variants count colorings only once when graph automorphisms relate them.
William Burnside: A British mathematician whose work included finite group theory and a theorem on counting group orbits. His orbit-counting lemma underlies the counting principle generalized by Pólya.
Inclusion–exclusion principle: A formula for counting elements in unions of sets by alternating sums of intersections. It handles overlapping constraints directly rather than encoding symmetries through cycle types.

Linked from 5 pages