Burnside's Lemma
Pillar: Fix — "Fix a symmetry \(g\). Count configurations UNCHANGED by \(g\). Average over all symmetries."
Pillar: Set — "Symmetries form a GROUP — a SET of operations closed under composition."
The Setup
You're making a necklace with 4 beads, each colored red or blue. How many distinct necklaces are there?
If the beads were in a line, the answer would be \(2^4 = 16\). But a necklace can be rotated. RRBB and RBBR are the same necklace — just rotate one bead clockwise.
You could try listing all 16 colorings and grouping the ones connected by rotation. Doable for 4 beads and 2 colors. Completely hopeless for 50 beads and \(10^9 + 7\) colors.
Burnside's lemma gives a formula that counts the distinct objects without listing them. The core idea: instead of grouping equivalent objects (hard), count how many objects each symmetry fixes (easy), and average.
The Key Idea
Forget necklaces for a moment and think about what "the same up to rotation" means.
You have a set of all possible colorings — call it \(X\). You have a set of symmetries — call it \(G\) (the group of rotations). Two colorings are "the same" if some symmetry in \(G\) transforms one into the other.
The number of truly distinct objects is the number of orbits — equivalence classes under the symmetry group. Burnside's lemma says:
where \(\text{Fix}(g)\) is the set of colorings unchanged by symmetry \(g\).
You're averaging the number of fixed points over all symmetries. That's it. The entire power of the lemma is that \(|\text{Fix}(g)|\) is usually easy to compute — much easier than counting orbits directly.
Formal Statement
Let \(G\) be a finite group acting on a finite set \(X\). For each \(g \in G\), define \(\text{Fix}(g) = \{x \in X : g \cdot x = x\}\). The number of distinct orbits is:
Burnside's lemma (also called the Cauchy-Frobenius lemma) is this formula. The proof uses double counting: count pairs \((g, x)\) where \(g\) fixes \(x\), once by summing over \(g\) and once by summing over \(x\). The orbit-stabilizer theorem connects the two sums.
Orbit-Stabilizer Intuition
For any element \(x \in X\), the stabilizer \(\text{Stab}(x)\) is the set of symmetries that fix \(x\). The orbit \(\text{Orb}(x)\) is the set of elements reachable from \(x\). The orbit-stabilizer theorem says:
This means elements in large orbits have small stabilizers. Burnside's lemma falls out by summing \(|\text{Stab}(x)|\) over all \(x\) and using the fact that each orbit of size \(s\) contributes \(s\) elements each with stabilizer size \(|G|/s\), totaling \(|G|\) per orbit.
Necklaces: The Cyclic Group
Back to the necklace problem. \(n\) beads, \(k\) colors, rotations only (no flips). The symmetry group is the cyclic group \(C_n = \{r_0, r_1, \ldots, r_{n-1}\}\), where \(r_d\) is rotation by \(d\) positions. So \(|G| = n\).
The question: for rotation \(r_d\), how many colorings are fixed?
A coloring is fixed by rotation-by-\(d\) if bead \(i\) and bead \((i + d) \bmod n\) always have the same color. Following the chain \(i \to i+d \to i+2d \to \cdots\) (mod \(n\)), you trace out a cycle of length \(n / \gcd(d, n)\). All beads in the same cycle must share a color.
The number of such cycles is \(\gcd(d, n)\). Each cycle can be any of \(k\) colors independently. So:
Burnside gives:
Worked Example: \(n = 4\), \(k = 2\)
| Rotation \(d\) | \(\gcd(d, 4)\) | \(|\text{Fix}(r_d)| = 2^{\gcd(d,4)}\) | |:---:|:---:|:---:| | 0 | 4 | \(2^4 = 16\) | | 1 | 1 | \(2^1 = 2\) | | 2 | 2 | \(2^2 = 4\) | | 3 | 1 | \(2^1 = 2\) |
List them: RRRR, BBBB, RRBB, RBRB, RRRB, BBBR. Six distinct necklaces.
The \(d = 0\) rotation is the identity — every coloring is fixed, so it contributes \(k^n\). This is always the largest term.
Optimizing the Sum
Instead of iterating over all \(d\) from \(0\) to \(n-1\), group rotations by their \(\gcd\) with \(n\). For each divisor \(g\) of \(n\), there are \(\phi(n/g)\) values of \(d\) with \(\gcd(d, n) = g\) (by a standard totient identity). So:
This reduces the sum from \(n\) terms to \(d(n)\) terms (the number of divisors), which is a massive speedup when \(n\) is large.
Grid Coloring: The Dihedral Group \(D_4\)
Color the cells of an \(n \times n\) grid with \(k\) colors. Two colorings are the same if one can be obtained from the other by rotation or reflection. How many distinct colorings?
The symmetry group is \(D_4\), the dihedral group of the square, with 8 elements:
| Symmetry | Description |
|---|---|
| \(e\) | Identity |
| \(r_{90}\) | Rotate 90 degrees |
| \(r_{180}\) | Rotate 180 degrees |
| \(r_{270}\) | Rotate 270 degrees |
| \(s_h\) | Reflect across horizontal axis |
| \(s_v\) | Reflect across vertical axis |
| \(s_{d1}\) | Reflect across main diagonal |
| \(s_{d2}\) | Reflect across anti-diagonal |
For each symmetry \(g\), you need \(|\text{Fix}(g)|\): how many \(k\)-colorings of the \(n \times n\) grid are unchanged by \(g\)?
Computing \(|\text{Fix}(g)|\) for Each Symmetry
Identity \(e\): Every coloring is fixed. \(|\text{Fix}(e)| = k^{n^2}\).
Rotation \(r_{90}\): Cell \((i, j)\) maps to \((j, n-1-i)\). Following the orbit: \((i,j) \to (j, n-1-i) \to (n-1-i, n-1-j) \to (n-1-j, i) \to (i,j)\). Each orbit has size 4 (except possibly a center cell when \(n\) is odd). The number of independent cells is \(\lceil n^2 / 4 \rceil\). So \(|\text{Fix}(r_{90})| = k^{\lceil n^2/4 \rceil}\).
Rotation \(r_{180}\): Each orbit has size 2 (a cell pairs with its 180-degree partner), except a center cell when \(n\) is odd. Independent cells: \(\lceil n^2 / 2 \rceil\). So \(|\text{Fix}(r_{180})| = k^{\lceil n^2/2 \rceil}\).
Rotation \(r_{270}\): Same orbit structure as \(r_{90}\). \(|\text{Fix}(r_{270})| = k^{\lceil n^2/4 \rceil}\).
Reflections (even \(n\)): For horizontal/vertical reflections, each cell pairs with its mirror. The number of independent cells is \(n^2 / 2\). For diagonal reflections, cells on the diagonal are fixed; others pair up. Independent cells: \(n^2/2 + n/2 = (n^2 + n)/2\).
Wait — let me be precise. For even \(n\): - Horizontal reflection: \(n^2 / 2\) independent cells. \(|\text{Fix}| = k^{n^2/2}\). - Vertical reflection: same. \(|\text{Fix}| = k^{n^2/2}\). - Main diagonal reflection: \(n(n+1)/2\) independent cells (the diagonal plus one side). Equivalently \((n^2 + n)/2\). \(|\text{Fix}| = k^{(n^2+n)/2}\). - Anti-diagonal reflection: same count. \(|\text{Fix}| = k^{(n^2+n)/2}\).
Reflections (odd \(n\)): All four reflections have \((n^2 + n)/2\) independent cells each. For axis reflections, the fixed set is the middle row (or column) of \(n\) cells. For diagonal reflections, the fixed set is the diagonal of \(n\) cells. The reasons differ, but the count is the same.
Worked Example: \(n = 2\), \(k = 2\)
| Symmetry | Independent cells | \(|\text{Fix}| = 2^{\text{cells}}\) | |:---:|:---:|:---:| | \(e\) | 4 | 16 | | \(r_{90}\) | 1 | 2 | | \(r_{180}\) | 2 | 4 | | \(r_{270}\) | 1 | 2 | | \(s_h\) | 2 | 4 | | \(s_v\) | 2 | 4 | | \(s_{d1}\) | 3 | 8 | | \(s_{d2}\) | 3 | 8 |
You can verify: the 16 possible 2x2 binary grids collapse into 6 equivalence classes under \(D_4\).
Why Burnside Works: The Double Counting Argument
Count the set \(S = \{(g, x) : g \in G, x \in X, g \cdot x = x\}\) in two ways.
Summing over \(g\): \(|S| = \sum_{g \in G} |\text{Fix}(g)|\).
Summing over \(x\): \(|S| = \sum_{x \in X} |\text{Stab}(x)|\).
By the orbit-stabilizer theorem, \(|\text{Stab}(x)| = |G| / |\text{Orb}(x)|\). All elements in the same orbit have the same orbit size. If there are \(N\) orbits, each orbit \(O\) contributes \(\sum_{x \in O} |G|/|O| = |G|\).
So \(|S| = N \cdot |G|\), which gives \(N = |S| / |G| = \frac{1}{|G|} \sum_{g \in G} |\text{Fix}(g)|\).
A Note on Polya Enumeration
Polya's enumeration theorem generalizes Burnside from "count distinct objects" to "count by weight" (e.g., how many necklaces have exactly 3 red and 2 blue beads?). It uses cycle index polynomials and is powerful but rarely needed in competitive programming. If you encounter a problem where you need to count by weight, the cycle index approach extends naturally from Burnside — but for this course, Burnside handles the problems you'll face.
The Code
Necklace Counting
Using modpow and modinv from Ch4:
long long modpow(long long base, long long exponent, long long mod) {
long long result = 1;
base %= mod;
while (exponent > 0) {
if (exponent & 1) result = result * base % mod;
base = base * base % mod;
exponent >>= 1;
}
return result;
}
long long modinv(long long value, long long mod) {
return modpow(value, mod - 2, mod);
}
long long countNecklaces(int beadCount, int colorCount, long long mod) {
long long totalFixed = 0;
for (int rotation = 0; rotation < beadCount; rotation++) {
int cycleCount = __gcd(rotation, beadCount);
totalFixed = (totalFixed + modpow(colorCount, cycleCount, mod)) % mod;
}
return totalFixed % mod * modinv(beadCount, mod) % mod;
}
\(O(n \log k)\) time (\(n\) rotations, each requiring one modpow call of \(O(\log k)\)). Can be optimized to \(O(d(n) \log k)\) by grouping rotations with the same GCD, using the totient-based formula.
Grid Counting (\(D_4\))
long long countGridColorings(int gridSize, int colorCount, long long mod) {
long long totalFixed = 0;
long long totalCells = (long long)gridSize * gridSize;
totalFixed = (totalFixed + modpow(colorCount, totalCells, mod)) % mod;
totalFixed = (totalFixed + modpow(colorCount, (totalCells + 3) / 4, mod)) % mod;
totalFixed = (totalFixed + modpow(colorCount, (totalCells + 1) / 2, mod)) % mod;
totalFixed = (totalFixed + modpow(colorCount, (totalCells + 3) / 4, mod)) % mod;
if (gridSize % 2 == 0) {
long long halfCells = totalCells / 2;
long long diagonalFree = (totalCells + gridSize) / 2;
totalFixed = (totalFixed + 2 * modpow(colorCount, halfCells, mod)) % mod;
totalFixed = (totalFixed + 2 * modpow(colorCount, diagonalFree, mod)) % mod;
} else {
long long reflectionFree = (totalCells + gridSize) / 2;
totalFixed = (totalFixed + 4 * modpow(colorCount, reflectionFree, mod)) % mod;
}
return totalFixed % mod * modinv(8, mod) % mod;
}
\(O(\log k)\) time — constant number of modpow calls regardless of grid size.
Common Mistakes
-
Forgetting the identity. The identity element (rotation by 0, "do nothing") always fixes every coloring. It's the largest term in the sum. If your Burnside answer is suspiciously small, check that you included it.
-
Wrong group size. Rotations only gives the cyclic group \(C_n\) with \(n\) elements. Rotations AND reflections gives the dihedral group \(D_n\) with \(2n\) elements. Dividing by the wrong \(|G|\) gives the wrong answer. Make sure you know which symmetries the problem considers.
-
Off-by-one in the GCD. The formula uses \(\gcd(d, n)\) where \(d\) ranges from \(0\) to \(n - 1\). Note \(\gcd(0, n) = n\), which gives the identity term \(k^n\). If you start your loop at \(d = 1\), you miss the identity contribution and undercount by \(k^n / n\).
Quick Recap
- Burnside's lemma: the number of distinct objects under symmetry group \(G\) is the average of \(|\text{Fix}(g)|\) over all \(g \in G\).
- Fix a symmetry, count what survives. For rotation by \(d\) on a necklace of \(n\) beads: \(|\text{Fix}| = k^{\gcd(d,n)}\).
- Necklaces (rotations only): \(\frac{1}{n} \sum_{d=0}^{n-1} k^{\gcd(d,n)}\). Optimize with totient grouping.
- Grids (\(D_4\)): 8 symmetries. Compute \(|\text{Fix}|\) for each rotation and reflection, average.
- Polya extends Burnside to weighted counting but is rarely needed in CP.
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CSES — Counting Necklaces | cses.fi/problemset/task/2209 | Medium | Direct Burnside on cyclic group |
| CSES — Counting Grids | cses.fi/problemset/task/2210 | Medium | Burnside on \(D_4\); careful orbit counting |
| CF 1255F — Point Ordering | codeforces.com/contest/1255/problem/F | Hard | Burnside with interactive query |
| CF 559C — Gerald and Giant Chess | codeforces.com/contest/559/problem/C | Medium-Hard | Counting under grid symmetry with obstacles |
Next: Putting It All Together — a decision tree for the entire course, mapping problem signals to the right tool.