Burnside's Lemma

Why Burnside's Lemma Matters

Suppose a design tool generates circular patterns with six positions and two named colors. With a marked starting position, there are $2^6=64$ color strings. Once the starting mark disappears, rotations describe the same design. How many distinct circular patterns remain?

Dividing $64$ by $6$ does not work. An all-one-color pattern has only one distinct rotation; a generic pattern has six. Burnside's lemma handles these different symmetry levels by counting what each transformation leaves unchanged. In this lesson, a necklace identifies rotations only. Reflections remain distinct unless they also happen to be rotations of the same pattern; adding reflections gives a different symmetry model, usually called a bracelet.

You will learn the general orbit-counting formula, specialize it to necklaces, trace every rotation, and implement the same modular algorithm in three languages. The proof uses finite sets and permutations; the implementation uses the Euclidean algorithm and repeated squaring rather than recursion or dynamic programming. The broader skill is recognizing when many representations describe one object.

Core Concepts and Terminology

Let $X$ be a finite set of labeled configurations and $G$ a finite group acting on it. An action specifies how every symmetry transforms a configuration, with the identity doing nothing and composition agreeing with successive transformations. An orbit contains all configurations reachable from one another by those symmetries. The set of orbits is written $X/G$.

For $g\in G$, define the fixed configurations by

$$ \operatorname{Fix}(g)=\{x\in X:g\cdot x=x\}. $$

Burnside's lemma states

$$ \lvert X/G\rvert=\frac{1}{\lvert G\rvert}\sum_{g\in G}\lvert\operatorname{Fix}(g)\rvert. $$

The word “fixed” refers to the entire configuration, not necessarily to individual positions. A rotation may move every position while preserving a coloring. This distinction is the bridge from geometry to counting; Stanford's group-action notes give the general formula and related coloring examples.

For necklaces of length $n\ge1$ using $c\ge0$ named colors, label positions $0,\ldots,n-1$. The rotation group is $C_n$, containing the $n$ shifts $r=0,\ldots,n-1$. Rotation $r$ sends position $i$ to $(i+r)\bmod n$. Following this permutation produces $d=\gcd(n,r)$ cycles, each of length $n/d$. In particular, the identity has $\gcd(n,0)=n$ cycles.

A coloring is fixed exactly when all positions in each cycle have the same color. Each cycle chooses independently from the $c$ colors, so

$$ \lvert\operatorname{Fix}(r)\rvert=c^{\gcd(n,r)},\qquad N(n,c)=\frac{1}{n}\sum_{r=0}^{n-1}c^{\gcd(n,r)}. $$

Why the greatest common divisor? A cycle closes at the smallest positive $t$ for which $tr$ is divisible by $n$, namely $t=n/\gcd(n,r)$. Dividing the $n$ positions by that cycle length gives $\gcd(n,r)$ cycles. The diagram below groups the $16$ binary strings of length $4$ into their six rotation orbits; the unequal orbit sizes explain why division of the raw count fails.

How Burnside's Lemma Works, Step by Step

First settle the equivalence relation. Here the allowed transformations are rotations, the color names stay distinct, and every position may use any color. Those assumptions determine the fixed-point formula. A different action or restrictions on colorings require a different fixed-point calculation.

The programs use the prime $p=1{,}000{,}000{,}007$ and accept $1\le n\lt p$ and $c\ge0$. The exact sum is a multiple of $n$, but it may be enormous. Reduce each term modulo $p$, then multiply the reduced sum by the modular inverse $n^{-1}\bmod p$. Fermat's little theorem gives $n^{-1}\equiv n^{p-2}\pmod p$ under the stated bounds.

1. Validate $n$ and $c$. Initialize a running residue $S=0$.
2. Visit each shift $r$ from $0$ through $n-1$, including the identity.
3. Compute $d=\gcd(n,r)$ using Euclid's algorithm.
4. Compute the fixed-coloring residue $f=c^d\bmod p$ using binary exponentiation.
5. Update $S\leftarrow(S+f)\bmod p$.
6. After all rotations, return $S\cdot n^{p-2}\bmod p$.

For the transition shown next, take $n=6$, $c=2$, and $r=2$. Positions split into cycles $(0\ 2\ 4)$ and $(1\ 3\ 5)$. Each cycle has two color choices, producing $2^2=4$ fixed colorings. After shifts $0$ and $1$, the exact running sum is $66$; processing shift $2$ increases it to $70$.

flowchart TD
    A["Read n and colors"] --> B{"Valid input bounds?"}
    B -- No --> C["Reject input"]
    B -- Yes --> D["Set sum = 0 and shift = 0"]
    D --> E{"shift less than n?"}
    E -- Yes --> F["cycles = gcd of n and shift"]
    F --> G["fixed = colors to cycles modulo p"]
    G --> H["Add fixed to sum modulo p"]
    H --> I["Increment shift"]
    I --> E
    E -- No --> J["Compute inverse of n modulo p"]
    J --> K["Return sum times inverse modulo p"]

Worked Example with a Full Trace

Count binary necklaces of length $n=6$ with $c=2$. Begin with $S=0$. No term or partial sum in this example reaches $p$, so the modular and exact sums agree.

1. For $r=0$, the cycles are $(0)(1)(2)(3)(4)(5)$. Thus $d=6$, the fixed count is $2^6=64$, and $S=64$.
2. For $r=1$, there is one cycle $(0\ 1\ 2\ 3\ 4\ 5)$. Thus $d=1$, the fixed count is $2$, and $S=66$.
3. For $r=2$, the cycles are $(0\ 2\ 4)(1\ 3\ 5)$. Thus $d=2$, the fixed count is $4$, and $S=70$.
4. For $r=3$, the cycles are $(0\ 3)(1\ 4)(2\ 5)$. Thus $d=3$, the fixed count is $8$, and $S=78$.
5. For $r=4$, the cycles are $(0\ 4\ 2)(1\ 5\ 3)$. Thus $d=2$, the fixed count is $4$, and $S=82$.
6. For $r=5$, there is one cycle $(0\ 5\ 4\ 3\ 2\ 1)$. Thus $d=1$, the fixed count is $2$, and $S=84$.

The exact average is

$$ N(6,2)=\frac{64+2+4+8+4+2}{6}=\frac{84}{6}=14. $$

The implementation computes $6^{-1}\bmod p=166{,}666{,}668$ and returns $84\cdot166{,}666{,}668\bmod p=14$. Every shift contributes once, even when several shifts have equal fixed counts. Equal counts do not make those group elements duplicates.

Implementation in Python, C++, and Java

Each panel is a complete program with the same samples, rotation loop, input validation, and modular answer. There is no input stream to configure. In Java, save the panel as Main.java. The functions count necklaces under rotations only; they do not count bracelets or list representatives.

The common portable input contract is $1\le n\lt p$ and a nonnegative color count that fits a signed $64$-bit integer. Python can also accept larger color integers. All programs reduce the color count before exponentiation. Zero colors give zero colorings for positive $n$; one color gives one necklace. Length zero is rejected because it is outside this rotation-average implementation's contract.

Python uses exact integer arithmetic. C++ uses long long and a multiplication bound: every modular operand is at most $p-1$, so every product is at most $(p-1)^2=1{,}000{,}000{,}012{,}000{,}000{,}036$, below the signed $64$-bit maximum. Java uses BigInteger for powers, sums, and inverse multiplication. The code returns a residue; it does not construct the potentially huge exact necklace count.

The identical output is: modulus = 1000000007; N(1,2) = 2; N(2,2) = 3; N(3,2) = 4; N(4,2) = 6; N(5,2) = 8; N(6,2) = 14; N(4,3) = 24; N(6,3) = 130; N(4,0) = 0; N(4,1) = 1; N(30,2) = 35792568.

from math import gcd

MOD = 1_000_000_007


def count_necklaces(n: int, colors: int) -> int:
    if not 1 <= n < MOD or colors < 0:
        raise ValueError("require 1 <= n < MOD and colors >= 0")
    base = colors % MOD
    total = 0
    for shift in range(n):
        cycles = gcd(n, shift)
        fixed = pow(base, cycles, MOD)
        total = (total + fixed) % MOD
    inverse_n = pow(n, MOD - 2, MOD)
    return total * inverse_n % MOD


def main() -> None:
    samples = [(1, 2), (2, 2), (3, 2), (4, 2), (5, 2),
               (6, 2), (4, 3), (6, 3), (4, 0), (4, 1), (30, 2)]
    print(f"modulus = {MOD}")
    for n, colors in samples:
        print(f"N({n},{colors}) = {count_necklaces(n, colors)}")


if __name__ == "__main__":
    main()

#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>

constexpr long long MOD = 1000000007LL;

int gcd_nonnegative(int a, int b) {
    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

long long mod_pow(long long base, long long exponent) {
    long long result = 1;
    base %= MOD;
    while (exponent > 0) {
        if (exponent % 2 == 1) result = result * base % MOD;
        base = base * base % MOD;
        exponent /= 2;
    }
    return result;
}

long long count_necklaces(int n, long long colors) {
    if (n < 1 || n >= MOD || colors < 0) {
        throw std::invalid_argument("require 1 <= n < MOD and colors >= 0");
    }
    long long base = colors % MOD;
    long long total = 0;
    for (int shift = 0; shift < n; ++shift) {
        int cycles = gcd_nonnegative(n, shift);
        long long fixed = mod_pow(base, cycles);
        total = (total + fixed) % MOD;
    }
    long long inverse_n = mod_pow(n, MOD - 2);
    return total * inverse_n % MOD;
}

int main() {
    const std::vector<std::pair<int, long long>> samples = {
        {1, 2}, {2, 2}, {3, 2}, {4, 2}, {5, 2},
        {6, 2}, {4, 3}, {6, 3}, {4, 0}, {4, 1}, {30, 2}
    };
    std::cout << "modulus = " << MOD << '\n';
    for (const auto& sample : samples) {
        int n = sample.first;
        long long colors = sample.second;
        std::cout << "N(" << n << ',' << colors << ") = "
                  << count_necklaces(n, colors) << '\n';
    }
    return 0;
}

import java.math.BigInteger;

public class Main {
    private static final int PRIME = 1_000_000_007;
    private static final BigInteger MOD = BigInteger.valueOf(PRIME);

    private static int gcdNonnegative(int a, int b) {
        while (b != 0) {
            int remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    public static BigInteger countNecklaces(int n, long colors) {
        if (n < 1 || n >= PRIME || colors < 0) {
            throw new IllegalArgumentException(
                    "require 1 <= n < MOD and colors >= 0");
        }
        BigInteger base = BigInteger.valueOf(colors).mod(MOD);
        BigInteger total = BigInteger.ZERO;
        for (int shift = 0; shift < n; ++shift) {
            int cycles = gcdNonnegative(n, shift);
            BigInteger fixed = base.modPow(BigInteger.valueOf(cycles), MOD);
            total = total.add(fixed).mod(MOD);
        }
        BigInteger inverseN = BigInteger.valueOf(n).modPow(
                MOD.subtract(BigInteger.TWO), MOD);
        return total.multiply(inverseN).mod(MOD);
    }

    public static void main(String[] args) {
        long[][] samples = {
            {1, 2}, {2, 2}, {3, 2}, {4, 2}, {5, 2},
            {6, 2}, {4, 3}, {6, 3}, {4, 0}, {4, 1}, {30, 2}
        };
        System.out.println("modulus = " + MOD);
        for (long[] sample : samples) {
            int n = (int) sample[0];
            long colors = sample[1];
            System.out.println("N(" + n + "," + colors + ") = "
                    + countNecklaces(n, colors));
        }
    }
}

Complexity, Correctness, and Invariants

For a general group action, Burnside's lemma requires a fixed-point count for every group element, or for representative types with their multiplicities. It does not automatically make those counts easy. If a group has $h$ elements and a fixed-point counter costs at most $T$, the straightforward evaluation takes $O(hT)$ time, plus the cost of generating the group and performing the final arithmetic.

For the necklace specialization, there are exactly $n$ iterations. Each greatest-common-divisor computation and each repeated-squaring power uses $O(\log(n+1))$ word operations; the final inverse costs $O(\log p)$. Thus a uniform upper bound is $O(n\log(n+1)+\log p)$ time with $O(1)$ modular working values. Under the fixed modulus, each value occupies a bounded number of bits. A variable modulus would require a bit-complexity analysis as well.

For a fixed $n$, changing the colors does not change the outer-loop count or the exponents. The best, average, and worst operation counts with respect to the color input therefore have the same asymptotic bound. There is always an $\Omega(n)$ loop cost; the displayed logarithmic bound accounts for arithmetic within those loops. An average over lengths requires a distribution and is not assumed here. Even though the contract allows lengths almost as large as $p$, iterating that many rotations may be impractical.

To prove the averaging rule, count pairs $(g,x)$ satisfying $g\cdot x=x$. Summing by transformations gives $\sum_{g\in G}\lvert\operatorname{Fix}(g)\rvert$. Summing by configurations gives $\sum_{x\in X}\lvert G_x\rvert$. Within one orbit, the orbit-stabilizer relation says each configuration has stabilizer size $\lvert G\rvert/\lvert\operatorname{Orb}(x)\rvert$. That orbit therefore contributes exactly $\lvert G\rvert$ pairs. Dividing the total by $\lvert G\rvert$ counts the orbits.

For the code, the cycle argument proves every term correct; the running-sum invariant proves all terms are accumulated. Finally, $p$ is prime and $1\le n\lt p$, so multiplication by the modular inverse is legitimate. An integral exact average does not, by itself, justify dividing its reduced numerator as an ordinary integer.

Variants, Pitfalls, and Optimizations

Rotations and reflections. Adding reflections changes the acting group to the dihedral group, of order $2n$ for the usual polygon action when $n\ge3$. For odd $n$, each reflection has $(n+1)/2$ cycles. For even $n$, half have $n/2+1$ cycles and half have $n/2$ cycles. Consequently, the reflection contribution to the fixed-point sum is

$$ R=\begin{cases} n\,c^{(n+1)/2},& n\text{ odd},\\ \frac{n}{2}\left(c^{n/2+1}+c^{n/2}\right),& n\text{ even}. \end{cases} $$

For $n\ge3$, the bracelet count is $(\sum_r c^{\gcd(n,r)}+R)/(2n)$. For binary length $6$, the rotation sum is $84$ and the reflection sum is $3(2^4+2^3)=72$, giving $156/12=13$ bracelets, compared with $14$ necklaces. This is a variant formula, not an option implemented by the code panels.

Group equal cycle types with their multiplicities. If $d$ divides $n$, exactly $\varphi(d)$ rotations have cycles of length $d$, where $\varphi$ is Euler's totient function. Reindexing the same sum gives

$$ N(n,c)=\frac1n\sum_{d\mid n}\varphi(d)c^{n/d}. $$

The multiplicities sum to $n$. Enumerating divisors can reduce the number of powers from $n$ to $\tau(n)$; include factorization, divisor generation, and totient calculation when assessing its total cost. Caching powers for repeated greatest common divisors is another improvement if retaining the rotation loop.

Restricted color inventories. A cycle must be monochromatic, but cycles no longer choose independently if a specified number of positions must receive each color. Count assignments of colors to entire cycles with the required totals, for example by coefficient extraction or dynamic programming. Likewise, adjacency constraints invalidate the unrestricted $c^{\text{cycles}}$ formula. The allowed configuration set must remain invariant under the chosen group.

Noninvertible group orders. If $n$ is divisible by $p$, the necklace count remains defined, but the code's inverse does not exist. One safe alternative is to compute the exact numerator with arbitrary-precision integers and divide before reducing. Another is to compute the numerator modulo $np$: its least nonnegative residue is divisible by $n$, and dividing that residue by $n$ gives the desired residue modulo $p$. That route requires arithmetic capable of handling the larger modulus; do not silently reuse the C++ multiplication bound. For an arbitrary modulus $m$, a modular inverse of the group order exists exactly when $\gcd(\lvert G\rvert,m)=1$.

Do not divide the raw configuration count. For binary length $4$, raw division gives $16/4=4$, but the six orbits have sizes $1,4,4,2,4,1$. Burnside instead averages fixed counts $16,2,4,2$, giving $6$. The next diagram contrasts these calculations and identifies the smaller orbits that make raw division fail.

Practice Problems and Real-World Use

For each task, identify the configuration set, list the allowed transformations, and check that they preserve the constraints. Derive a fixed-point count before writing the average. The small targets below can be checked by enumerating strings or colorings and selecting one representative per orbit; larger versions reward grouping by cycle type.

A useful independent verifier generates every short color string, forms all its rotations, and stores the lexicographically smallest rotation in a set. The set size must match Burnside's answer. Keep this verifier small enough to exhaust all configurations; its role is to detect mistakes in the action, cycle counts, or arithmetic, while the lemma supplies the scalable counting argument.