Burnside's Lemma

Why Burnside matters

Counting "up to symmetry" is a recurring task: how many distinct necklaces, colored cubes, molecular isomers, switching networks, or graph labelings are there if we identify configurations that differ by a symmetry? Naive enumeration overcounts each true configuration by exactly the size of its stabilizer subgroup, and stabilizers vary across configurations — so simple division does not work. Burnside's lemma is the trick that makes the count tractable: average fixed-point counts over the group instead of dividing.

• Enumeration up to symmetry. Whenever you have a group acting on a set of structures and want orbit count — count "essentially distinct" things — Burnside is the first tool. Pólya's enumeration theorem refines it when you also want generating-function output (number of orbits with prescribed weight statistics).
• Chemistry — isomer counting. Pólya's original 1936 motivation. The number of structural isomers of an alkane C_n H_{2n+2} is the number of orbits of n-vertex 4-regular trees under the natural label group; Pólya enumeration handles this. Modern cheminformatics still uses cycle-index machinery for isomer enumeration.
• Coding theory. Equivalence classes of codes under permutations of coordinates, error-correcting codes up to isomorphism, and weight enumerators all use Burnside / Pólya.
• Switching networks. Boolean function classification — how many distinct n-input Boolean functions are there up to permutations of inputs? — uses Burnside on the symmetric group acting on truth tables.
• Graph theory. Counting unlabeled graphs is an iconic Burnside / Pólya application: |unlabeled graphs on n vertices| = |labeled graphs| / |aut| where the average is taken via Burnside on S_n acting on edge sets. This gives the Erdős-Pólya asymptotic 2^(C(n, 2)) / n!.
• Crystallography and design theory. Counting symmetry classes of designs, matrix decompositions, and combinatorial geometries on lattices.
• Game theory and bracket problems. Counting distinct tournaments up to relabeling teams, distinct seedings of brackets, or distinct rotations of round-robin schedules.

Proof sketch (the double-counting argument)

Let G be a finite group acting on a finite set X. Define the set S = {(g, x) : g · x = x} of fixed-point incidences. We count |S| in two ways.

• By g. For each g ∈ G, Fix(g) is exactly the set of x with (g, x) ∈ S. So |S| = Σ_{g ∈ G} |Fix(g)|.
• By x. For each x ∈ X, Stab(x) = {g : g · x = x} is the stabilizer subgroup. So |S| = Σ_{x ∈ X} |Stab(x)|.

By the orbit-stabilizer theorem, |Stab(x)| · |Orbit(x)| = |G|, so |Stab(x)| = |G| / |Orbit(x)|. Sum over x: Σ_{x ∈ X} |G| / |Orbit(x)| = |G| · Σ_{orbits O} Σ_{x ∈ O} (1 / |O|) = |G| · (number of orbits). Equating the two expressions for |S| and dividing by |G| gives Burnside's identity. The whole proof is two pages, no machinery beyond orbit-stabilizer.

Worked examples

• Necklaces with 6 beads, 3 colors, rotation group C_6. Divisors of 6: {1, 2, 3, 6}; Euler totients φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(6) = 2. Distinct necklaces = (1/6)(1 · 3^6 + 1 · 3^3 + 2 · 3^2 + 2 · 3^1) = (1/6)(729 + 27 + 18 + 6) = 130.
• Bracelets with 6 beads, 3 colors, dihedral group D_6. Add reflections to the cyclic count. Six reflections; for n even, three pass through opposite vertices (cycle 2-cycles plus 2 fixed beads, fixed colorings = c^4 = 81) and three through opposite edges (cycle 2-cycles only, fixed = c^3 = 27). Total = (1/12)(729 + 27 + 18 + 6 + 3 · 81 + 3 · 27) = (1/12)(780 + 243 + 81) = (1/12)(1104) = 92.
• Colorings of the cube faces with 2 colors. Cube rotation group has 24 elements. Cycle index Z = (1/24)(a_1^6 + 6 a_1^2 a_4 + 3 a_1^2 a_2^2 + 8 a_3^2 + 6 a_2^3). Substitute a_i = 2: (1/24)(2^6 + 6 · 2^3 + 3 · 2^4 + 8 · 2^2 + 6 · 2^3) = (1/24)(64 + 48 + 48 + 32 + 48) = 240/24 = 10.
• Coloring 4 corners of a square, 2 colors, rotation C_4. (1/4)(2^4 + 2^1 + 2^2 + 2^1) = (1/4)(16 + 2 + 4 + 2) = 6 distinct colorings.
• Coin-arrangement on a circle. n indistinguishable coins on a regular n-gon up to rotation, c colors: (1/n) Σ_{d | n} φ(d) c^(n/d). Direct application.

The cycle index polynomial

To make Pólya's refinement explicit, introduce variables a_1, a_2, … and define the cycle index of a group G acting on n elements:

Z(G; a_1, a_2, …) = (1/|G|) Σ_{g ∈ G} ∏_i a_i^{c_i(g)}.

Here c_i(g) is the number of i-cycles in the disjoint-cycle decomposition of g. Substituting a_i = c gives Burnside's count for c-color colorings. Substituting a_i = (x_1^i + x_2^i + ⋯ + x_c^i) — the i-th power-sum — gives the multivariate orbit-generating function in which the coefficient of x_1^{n_1} ⋯ x_c^{n_c} is the number of orbits with exactly n_j beads of color j.

Standard cycle indices:

• Cyclic group C_n. Z(C_n) = (1/n) Σ_{d | n} φ(d) a_d^{n/d}.
• Dihedral group D_n. Cyclic part plus reflections. For n odd: + (1/2) a_1 a_2^{(n−1)/2}. For n even: + (1/4)(a_1^2 a_2^{(n−2)/2} + a_2^{n/2}).
• Symmetric group S_n. Sum over conjugacy classes (partitions of n) weighted by class size; encodes set partitions of {1, …, n}.
• Alternating group A_n. Even permutations of S_n.

Common misconceptions

• "Needs G abelian." Burnside works for any finite group action, abelian or not. The cube rotation group (order 24, isomorphic to S_4) is non-abelian; Burnside still applies.
• "Complicated to compute." The lemma reduces an orbit count to fixed-point counts for individual group elements, often dramatically simpler. For symmetric groups acting nicely, the sum is by conjugacy classes — at most a partition-of-n count of terms.
• "Burnside's first proof." Cauchy proved it in 1845. Frobenius generalized in 1887. Burnside (1897) popularized it without attribution; modern texts increasingly write "Cauchy-Frobenius lemma" or "orbit-counting theorem".
• "Average fixed-point count is the orbit count." Strictly true only when G is finite. The infinite-group analogue requires Haar measure on G (compact case) — measure of fixed-point set replaces fraction of group elements that fix a point.
• "Pólya enumeration is just Burnside." Pólya's theorem refines Burnside by tracking weights / colors, not just counts. The cycle index polynomial encodes the action structurally, allowing multivariate generating-function output.
• "Stabilizers must be the same size." Different orbits can have stabilizers of different sizes. Burnside averages over the group, not over the orbits — this avoids the size-of-stabilizer trap.