Burnside's Lemma and Pólya Enumeration

Counting objects up to symmetry — necklaces, colourings, board positions that are equivalent under rotation or reflection.

Burnside’s lemma

$|X/G|=\frac{1}{|G|}{\sum }_{g\in G}|X^g|,$

where $X^g$ is the set of objects fixed by the symmetry $g$.

The number of distinct objects equals the average number of objects fixed by each symmetry.

Counting fixed points is usually easy; counting orbits directly is not. That asymmetry is the whole value of the lemma.

The canonical example: necklaces

Count necklaces of $n$ beads in $k$ colours, up to rotation. The group is the $n$ rotations. A rotation by $d$ fixes a colouring iff the colouring is constant on each cycle of that rotation — and rotation by $d$ has $\gcd (n,d)$ cycles. So:

$\frac{1}{n}{\sum }_{d=0}^{n-1}{k}^{\gcd (n,d)}=\frac{1}{n}{\sum }_{d\mid n}\phi \left(\frac{n}{d}\right)k^d.$

long long necklaces(long long n, long long k, long long MOD) {
    long long total = 0;
    for (long long d = 1; d * d <= n; d++) {
        if (n % d) continue;
        total = (total + phi(n / d) % MOD * powmod(k, d, MOD)) % MOD;
        if (d != n / d) total = (total + phi(d) % MOD * powmod(k, n / d, MOD)) % MOD;
    }
    return total % MOD * modinv(n % MOD, MOD) % MOD;
}

$O(\sqrt{n}\log )$ — and it handles $n$ up to $10^9$.

With reflections — the dihedral group

Add the $n$ reflections ($|G|=2n$):

• $n$ odd: every reflection has $\frac{n+1}{2}$ cycles, contributing $n{k}^{(n+1)/2}$.
• $n$ even: $\frac{n}{2}$ reflections through opposite vertices give $k^{n/2+1}$ each, and $\frac{n}{2}$ through edge midpoints give $k^{n/2}$ each.

$\text{bracelets}=\frac{1}{2n}\left({\sum }_{d\mid n}\phi (n/d)k^d+\{\begin{array}{ll}n{k}^{(n+1)/2}& n\text{ odd}\\ \frac{n}{2}\left(k^{n/2}+k^{n/2+1}\right)& n\text{ even}\end{array}\right).$

The recipe

1. Identify the group $G$ of symmetries (rotations, reflections, permutations of coordinates…).
2. For each $g\in G$, decompose its action on the positions into cycles.
3. A colouring is fixed by $g$ iff it is constant on every cycle, so $|X^g|=k^{c(g)}$ where $c(g)$ is the cycle count.
4. Average over $G$.

When $|G|$ is small (a square’s 8 symmetries, a cube’s 24), just enumerate the group elements and count cycles directly.

Pólya enumeration theorem

The refinement that tracks how many of each colour. Define the cycle index

$Z_G(x_1,\dots ,x_n)=\frac{1}{|G|}{\sum }_{g\in G}{\prod }_i{x}_i^{c_i(g)},$

where $c_i(g)$ is the number of $i$-cycles of $g$. Then substituting $x_i\to {\sum }_j{y}_j^i$ gives a generating function whose coefficient of $\prod y_j^{m_j}$ counts colourings using exactly $m_j$ of colour $j$.

Burnside is Pólya with all $y_j=1$.

Example. Necklaces with exactly $a$ black and $b$ white beads, up to rotation:

$\frac{1}{n}{\sum }_{d\mid \gcd (a,b)}\phi (d)\left(\genfrac{}{}{0ex}{}{n/d}{a/d}\right).$

Common groups and their cycle counts

Object	Group	Order	Cycle structure
Necklace, rotations	$C_n$	$n$	rotation by $d$: $\gcd (n,d)$ cycles
Bracelet, + reflections	$D_n$	$2n$	as above
Square grid, rotations	$C_4$	4	positions in 4-cycles (centre fixed)
Square grid, + reflections	$D_4$	8
Cube faces	rotations	24	6 faces under 24 rotations
Cube vertices	rotations	24
Unordered pairs / graphs	$S_n$ acting on edges	$n!$	hard; needs Pólya

Counting non-isomorphic graphs on $n$ vertices is Pólya applied to $S_n$ acting on the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges — feasible for $n\le 10$ or so by enumerating conjugacy classes (integer partitions of $n$).

Practical notes

• The division by $|G|$ needs a modular inverse — make sure $\gcd (|G|,\text{MOD})=1$ (true for $\text{MOD}=10^9+7$ unless $|G|$ is a multiple of it).
• Sum over divisors rather than all group elements whenever the group is cyclic — that turns $O(n)$ into $O(\sqrt{n})$.
• For small explicit groups, brute-force the cycle counts; it is less error-prone than deriving formulas.

See also: Combinatorics · Euler Totient · Special Numbers