Pólya Enumeration Theorem
The Pólya Enumeration Theorem (PET) generalizes Burnside's lemma by incorporating a weight function on colorings. It provides a powerful generating function for counting distinct colorings under group symmetry, with applications throughout combinatorics, chemistry, and computer science.
The Theorem
Given a group acting on a set of positions, and a set of colors (range) with a weight function , the figure counting series enumerates distinct colorings by weight. If the generating function for the colors is , then the Pólya Enumeration Theorem expresses the generating function for distinct colorings.
The inventory (or pattern inventory) of colorings under a group action is obtained by substituting the figure counting series into the cycle index. If the "figure series" is (one term per color), the inventory is:
Count 4-bead necklaces with red () and blue () beads, tracked by color composition. Using , substitute : There is 1 necklace each of types , , , , and 2 necklaces of type .
The Dihedral Group
The dihedral group of order acts on positions by rotations and reflections. Its cycle index is:
A bracelet is a necklace considered up to both rotation and reflection. For 6-bead bracelets with 3 colors, the total count is distinct bracelets.
The PET is essential in chemical enumeration: counting isomers of molecules. For example, the number of distinct substituted benzene rings is computed using with two colors (H and X). For dichlorobenzene (), there are exactly 3 isomers (ortho, meta, para).