cycleindex

Cycle index is a polynomial associated with a permutation group acting on a finite set, used to encode how the group's elements decompose into cycles and to count distinct configurations under symmetry. It plays a central role in Polya’s enumeration theorem, which translates symmetry information into counting formulas for colorings and other labeled structures.

Formally, let G be a finite group acting on a set X of size n. For each g in G, c_k(g) denotes the number of k-cycles in the permutation of X induced by g. The cycle index Z_G is defined by

Z_G = (1/|G|) sum_{g in G} ∏_{k≥1} a_k^{c_k(g)},

where a_k are indeterminates. Z_G is a symmetric polynomial in the variables a_k and aggregates the cycle-type distribution of all group elements.

Interpretation and usage: If one colors the elements of X with c colors and asks for the number of colorings up to G-symmetry, substitute a_k = c for all k in Z_G. The resulting value, by Polya’s theorem, equals the number of distinct colorings under the action of G.

Examples: For the symmetric group S_3 acting on three points, Z_{S_3} = (1/6)(a1^3 + 3 a1 a2 + 2 a3). For the cyclic group C_n acting on n beads in a circle (rotations only), Z_{C_n} = (1/n) sum_{d|n} φ(d) a_d^{n/d}, where φ is Euler’s totient function.

Applications include counting colorings and configurations up to symmetry in chemistry, combinatorics, and design of necklaces and bracelets.