Burnside's Lemma — Orbit Counting & Symmetry Groups

January 2026 · 22 min read

Introduction

Suppose you need to count the number of distinct necklaces you can make with n beads and k colours, where two necklaces are the same if one can be rotated into the other. Naively iterating over all kⁿ colourings and deduplicating is far too slow for competitive-programming constraints (n up to 10⁹). Burnside's Lemma turns this exponential brute force into a clean O(n) — or even O(√n) — summation.

Historically the result is due to Cauchy (1845) and Frobenius (1887); Burnside merely popularized it in his 1897 textbook. It is sometimes called the Cauchy–Frobenius lemma or the orbit-counting theorem. Despite the naming controversy, the competitive-programming community universally calls it "Burnside's Lemma."

The Theorem

Definitions

Let X be a finite set (the set of all colourings) and G a finite group that acts on X (the symmetry group). For each element g ∈ G, define the fixed-point set:

Fix(g) = { x ∈ X : g · x = x }

An orbit of x ∈ X is the set { g · x : g ∈ G }. Two elements in the same orbit are "equivalent under G." The number of distinct orbits is written |X/G|.

Formal Statement

|X/G| = (1 / |G|) · Σ_g∈G |Fix(g)|

In words: the number of distinct objects equals the average number of colourings fixed by each group element. This is remarkable — instead of grouping colourings into orbits (hard), we simply count fixed points of each symmetry (easy) and average.

Proof Sketch (Double Counting)

Count the set S = { (g, x) ∈ G × X : g · x = x } in two ways. Summing over G gives Σ_g |Fix(g)|. Summing over X gives Σ_x |Stab(x)|, where Stab(x) is the stabiliser of x. By the orbit-stabiliser theorem, |Stab(x)| = |G| / |Orb(x)|. Grouping by orbits:

Σ_x |G| / |Orb(x)| = |G| · Σ_{orbits O} Σ_{x ∈ O} 1/|O| = |G| · (number of orbits).

Equating both sides and dividing by |G| yields the lemma. ■

Symmetry Groups for CP

Cyclic Group C_n (Rotations Only)

The rotations of a regular n-gon form the cyclic group C_n = { r⁰, r¹, …, rⁿ⁻¹ }, where rⁱ denotes rotation by i · 360°/n. The group has order n.

For a rotation rⁱ acting on an n-bead necklace with k colours, a colouring is fixed if and only if it is periodic with period gcd(i, n). Hence:

|Fix(rⁱ)| = k^gcd(i,n)

The full Burnside formula under cyclic rotations becomes:

|X/C_n| = (1/n) · Σ_i=0ⁿ⁻¹ k^gcd(i,n)

Optimisation via Divisors

Since gcd(i, n) depends only on the divisor d = gcd(i, n), we can group terms by d | n. For each divisor d of n, there are φ(n/d) values of i with gcd(i, n) = d (where φ is Euler's totient). So:

|X/C_n| = (1/n) · Σ_d|n φ(n/d) · k^d

This reduces the summation from n terms to O(√n) terms (the number of divisors), which is crucial when n can be up to 10⁹.

Dihedral Group D_n (Rotations + Reflections)

For bracelets (necklaces that can also be flipped), the symmetry group is D_n with |D_n| = 2n. It contains the n rotations from C_n plus n reflections. The reflection fixed-point counts differ for odd and even n:

Interactive Visualization

Below we animate Burnside's Lemma on a 4-bead necklace with 2 colours. There are 2⁴ = 16 total colourings and 4 rotations (C₄). Step through each rotation to see which colourings it fixes, then watch the final orbit count emerge.

Click Step to apply each rotation and count fixed colourings.

Worked Examples

Example 1 — Necklace with n=4 beads, k=2 colours (rotations only)

Group: C₄ = { r⁰, r¹, r², r³ }.

• r⁰ (identity): every colouring is fixed → |Fix| = 2⁴ = 16.
• r¹ (90°): fixed iff all beads same colour → |Fix| = 2^gcd(1,4) = 2¹ = 2.
• r² (180°): fixed iff opposite beads match → |Fix| = 2^gcd(2,4) = 2² = 4.
• r³ (270°): same as r¹ by symmetry → |Fix| = 2¹ = 2.

|X/G| = (16 + 2 + 4 + 2) / 4 = 24 / 4 = 6 distinct necklaces.

Example 2 — n = 6 beads, k = 3 colours, rotations only

Divisors of 6: {1, 2, 3, 6}. Using the optimised formula:

• d=1: φ(6) = 2, contributes 2 · 3¹ = 6
• d=2: φ(3) = 2, contributes 2 · 3² = 18
• d=3: φ(2) = 1, contributes 1 · 3³ = 27
• d=6: φ(1) = 1, contributes 1 · 3⁶ = 729

|X/C₆| = (6 + 18 + 27 + 729) / 6 = 780 / 6 = 130

Example 3 — Codeforces-Style Problem

This is exactly the necklace-counting formula under C_n. Since n can be 10⁹, we must use the divisor-based optimisation. Enumerate divisors d of n in O(√n), compute φ(n/d) and k^d mod p for each, sum up, and multiply by the modular inverse of n.

C++ Implementation

Core Utilities

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long modinv(long long a, long long mod) {
    return power(a, mod - 2, mod);  // Fermat's little theorem
}

long long euler_phi(long long n) {
    long long result = n;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

Necklace Counting (Rotations — C_n)

long long burnside_necklace(long long n, long long k) {
    // |X/C_n| = (1/n) * sum over d|n of phi(n/d) * k^d
    long long ans = 0;
    for (long long d = 1; d * d <= n; ++d) {
        if (n % d != 0) continue;
        // divisor pair: d and n/d
        ans = (ans + euler_phi(n / d) % MOD * power(k, d, MOD)) % MOD;
        if (d != n / d) {
            ans = (ans + euler_phi(d) % MOD * power(k, n / d, MOD)) % MOD;
        }
    }
    ans = ans % MOD * modinv(n % MOD, MOD) % MOD;
    return ans;
}

Bracelet Counting (Rotations + Reflections — D_n)

long long burnside_bracelet(long long n, long long k) {
    // Start with the rotation sum (C_n contribution)
    long long rot = 0;
    for (long long d = 1; d * d <= n; ++d) {
        if (n % d != 0) continue;
        rot = (rot + euler_phi(n / d) % MOD * power(k, d, MOD)) % MOD;
        if (d != n / d)
            rot = (rot + euler_phi(d) % MOD * power(k, n / d, MOD)) % MOD;
    }

    // Reflection contribution
    long long ref = 0;
    if (n % 2 == 1) {
        // all n reflections: each fixes k^((n+1)/2)
        ref = (long long)(n % MOD) * power(k, (n + 1) / 2, MOD) % MOD;
    } else {
        // n/2 axis-through-vertices reflections: k^(n/2+1) each
        // n/2 axis-through-edges reflections:    k^(n/2)   each
        long long half = n / 2 % MOD;
        ref = half * power(k, n / 2 + 1, MOD) % MOD;
        ref = (ref + half * power(k, n / 2, MOD)) % MOD;
    }

    long long total = (rot + ref) % MOD;
    total = total * modinv(2 * n % MOD, MOD) % MOD;
    return total;
}

Main — Reading Input and Solving

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, k;
    cin >> n >> k;

    cout << burnside_necklace(n, k) << "\n";
    // For bracelets: cout << burnside_bracelet(n, k) << "\n";
    return 0;
}

Common Patterns & Pitfalls

Burnside vs Pólya

Use Burnside when you only need the total count. Switch to Pólya when the problem asks for counts filtered by colour frequency or a generating-function approach.

Pitfall 1 — Forgetting the Modular Inverse

The formula divides by |G|. Under modular arithmetic, you must use modinv(|G|, MOD). Integer division will produce wrong answers.

Pitfall 2 — Incorrect Euler Phi

A common mistake is implementing φ with result -= result / p but forgetting to fully divide out p from n first. The standard sieve-style implementation above is correct; study it carefully.

Pitfall 3 — Bracelet vs Necklace

Problems that say "necklace" sometimes mean rotations only, sometimes rotations and reflections (bracelet). Read the statement carefully. If flipping is allowed, the group is D_n, not C_n, and the answer is smaller.

Pitfall 4 — Overcounting with Non-Standard Groups

Some problems define custom equivalences (e.g., two colourings of a cube are the same under any rotation of the cube). You must correctly enumerate the symmetry group. For a cube the rotation group has 24 elements; for a regular tetrahedron, 12.

Practice Problems

1. Codeforces 474F — Columns — Burnside on grid colourings with cyclic shifts.
2. CSES — Counting Necklaces — Classic necklace counting under rotation (C_n).
3. CSES — Counting Grids — 2D grid colourings under the 4-rotation group.
4. SPOJ — TICTACTO — Count distinct tic-tac-toe boards under the dihedral group of the square.
5. AtCoder ABC198 F — Cube — Burnside on 3D rotations of a cube.
6. Codeforces Gym 100162 — Assorted Burnside/Pólya problems for practice.