PolyaEnumeration

Polya enumeration, or Polya's enumeration theorem, is a set of techniques in combinatorics for counting distinct configurations of objects that are considered equivalent under symmetry. It was developed by George Pólya and provides a systematic way to count inequivalent colorings, arrangements, or other labeled structures when a finite group acts on the set of positions.

The key tool is the cycle index polynomial Z_G of a finite permutation group G acting on n positions. For each group element g, write its cycle decomposition; c_i(g) is the number of i-cycles. Then Z_G = (1/|G|) sum_{g in G} ∏_i x_i^{c_i(g)}. If we have q colors, the number of distinct colorings up to G is Z_G evaluated at x_i = q for all i (equivalently the average of q^{number of cycles of g} over g).

Polya's theorem generalizes Burnside's lemma and yields a unified framework. It also allows counting colorings with restrictions or weighted colors by substituting different expressions for x_i; the cycle index acts as a generating function for the symmetry-adapted counts.

Common examples include counting colorings of beads on a necklace (rotations only: cyclic group C_n) or a bracelet (rotations and reflections: dihedral group D_n). The cycle index of C_n is Z_{C_n} = (1/n) sum_{d|n} φ(d) x_d^{n/d}.

Applications span chemistry for counting stereoisomers, crystallography, tilings, and other combinatorial enumeration problems. Polya enumeration emphasizes the role of symmetry in reducing the number of distinct configurations.