maths2u
PhysicsMathsChemistryBiology
Tier
⌕ Search ⌘K
Theorem

Burnside's counting lemma

T-125Home MU-402Threads structure
Statement

Let \(G\) be a finite group acting on a finite set \(X\). For \(g \in G\) write \(X^g = \{x \in X : g \cdot x = x\}\) for the fixed-point set of \(g\), and let \(X/G\) denote the set of orbits of the action. Then the number of orbits is the average number of points fixed by each group element: \[ |X/G| \;=\; \frac{1}{|G|}\sum_{g \in G} |X^g|. \]

Why it matters

Counting orbits directly is often hopeless: one must partition \(X\) by hand and hope not to double-count. Burnside's lemma converts this combinatorial problem into an averaging problem over the group, where each term \(|X^g|\) is frequently easy to compute from the cycle structure of \(g\). This is the engine behind the Pólya enumeration theorem, which extends the lemma with generating functions to count colourings, necklaces, graphs up to symmetry, and chemical isomers.

Structurally, the lemma is the first serious application of the orbit-counting idea that pervades representation theory: it is literally the statement that the number of orbits equals the multiplicity of the trivial representation inside the permutation representation \(\mathbb{C}[X]\), which is why it sits naturally in a representation theory unit rather than purely in combinatorics.

Hypotheses
\(G\) is a finite group.If \(G\) is infinite the sum \(\sum_{g\in G}|X^g|\) need not converge or even make sense as a finite average; e.g. \(G = \mathbb{Z}\) acting on \(X=\{1,\dots,n\}\) by a permutation of infinite order has no natural "average" over infinitely many group elements. \(X\) is a finite set.If \(X\) is infinite, \(|X^g|\) and \(|X/G|\) may both be infinite cardinals, and the identity \(|X/G| = \frac{1}{|G|}\sum_g |X^g|\) loses its counting meaning (division by \(|G|\) on infinite cardinals is not well-defined in the required sense). The action is a genuine group action (i.e. \(g\cdot(h\cdot x) = (gh)\cdot x\) and \(e \cdot x = x\)).Without the action axioms the stabiliser subgroup argument breaks: orbit–stabiliser (used inside the proof) requires that stabilisers actually be subgroups, which relies on associativity and the identity axiom.
Proof
1
\[ \sum_{g \in G} |X^g| = \sum_{g \in G} \sum_{x \in X} \mathbf{1}[g \cdot x = x] = \sum_{x \in X} \sum_{g \in G} \mathbf{1}[g\cdot x = x] \]
Double-count the pairs \((g,x)\) with \(g\cdot x = x\) by summing the indicator \(\mathbf{1}[g\cdot x=x]\) over the finite index set \(G \times X\) in either order (Fubini for finite sums, i.e. finite double summation commutes freely). A
2
\[ \sum_{g\in G} \mathbf{1}[g\cdot x = x] = |\{g \in G : g \cdot x = x\}| = |G_x| \]
By definition the stabiliser of \(x\) is \(G_x = \{g \in G : g\cdot x = x\}\); the inner sum simply counts its elements. \(G_x\) is a subgroup of \(G\) (closed under products and inverses by the group action axioms), so \(|G_x|\) divides \(|G|\) by Lagrange's theorem — this will be used in Step 3. A
3
\[ |G_x| = \frac{|G|}{|Gx|}, \qquad \text{where } Gx = \{g\cdot x : g \in G\} \text{ is the orbit of } x. \]
This is the Orbit–Stabiliser Theorem: the map \(gG_x \mapsto g\cdot x\) from left cosets of \(G_x\) to the orbit \(Gx\) is a well-defined bijection (well-defined and injective because \(g\cdot x = h\cdot x \iff g^{-1}h \in G_x \iff gG_x = hG_x\); surjective onto \(Gx\) by definition of orbit). Hence \(|Gx| = [G:G_x] = |G|/|G_x|\) by Lagrange. B
4
\[ \sum_{g\in G}|X^g| = \sum_{x \in X} |G_x| = \sum_{x\in X} \frac{|G|}{|Gx|} \]
Substitute Step 3 into the outer sum obtained in Step 1. A
5
\[ \sum_{x \in X} \frac{1}{|Gx|} = \sum_{O \in X/G}\ \sum_{x \in O} \frac{1}{|O|} = \sum_{O\in X/G} |O|\cdot\frac{1}{|O|} = \sum_{O \in X/G} 1 = |X/G| \]
Regroup the sum over \(x \in X\) by orbit: the orbits partition \(X\) (orbits of a group action are equivalence classes of the relation \(x \sim y \iff \exists g, g\cdot x = y\), which is reflexive by \(e\cdot x=x\), symmetric by invertibility of \(g\), transitive by closure under products). For \(x\) in a fixed orbit \(O\), \(Gx = O\), so each of the \(|O|\) elements of \(O\) contributes \(1/|O|\) to the sum, totalling \(1\) per orbit. C
6
\[ \sum_{g\in G} |X^g| = |G| \sum_{x\in X}\frac{1}{|Gx|} = |G|\cdot |X/G| \]
Combine Step 4 (factor \(|G|\) out of the sum, valid since it is a common constant factor) with Step 5. Dividing both sides by \(|G| \gt 0\) gives \(|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|\), the claimed identity. B
Result
\[ |X/G| = \frac{1}{|G|}\sum_{g\in G} |X^g| \]

Reading. The number of distinct orbits equals the average, taken over all group elements, of the number of points each element leaves fixed.

Scope. Applies to any action of a finite group \(G\) on a finite set \(X\). Extends verbatim to actions on a set of colourings, labelled graphs, necklaces, etc., wherever \(G\) acts by permuting a finite structure; combined with generating functions it becomes the Pólya Enumeration Theorem for weighted counting.

Corollaries & converses
  • If \(G\) acts freely (only \(e\) has fixed points, i.e. \(X^g = \varnothing\) for \(g \neq e\)), the lemma reduces to \(|X/G| = |X|/|G|\), recovering the free-action orbit count directly.
  • If \(G\) acts transitively, \(|X/G| = 1\), so \(\sum_{g} |X^g| = |G|\): the fixed points sum exactly to the group order, a fact used to bound transitive permutation representations.
  • The identity \(\sum_{g\in G}|X^g| = |G|\cdot|X/G|\) shows \(\frac{1}{|G|}\sum_g |X^g|\) is always a non-negative integer, a non-obvious arithmetic fact about the fixed-point counts that is otherwise not evident.
  • No converse in the usual sense: the lemma is an identity, not an implication, so there is nothing to invert. However, it does not say each individual \(g\) fixes the average number of points — that average is a property of the whole group, not of any single element, and assuming otherwise is a common error (see below).
Fails without
  • Finiteness of \(G\) dropped: take \(G = \mathrm{SO}(2)\) acting on \(X = S^1\) by rotation. Every non-identity rotation fixes no point (\(X^g=\varnothing\)), only \(e\) fixes everything (\(X^e = S^1\), infinite), and there is exactly one orbit (\(X/G\) is a single orbit, in fact the whole action is transitive). The "average" \(\frac{1}{|G|}\sum_g|X^g|\) is meaningless since \(G\) is uncountable and \(|G|=\infty\); no finite-sum formula survives.
  • Finiteness of \(X\) dropped: let \(G = \mathbb{Z}/2\) act on \(X = \mathbb{Z}\) by \(g\cdot n = -n\). Then \(X^e = \mathbb{Z}\) is infinite and \(X^g = \{0\}\) for the non-identity \(g\); the orbits are \(\{0\}\) and \(\{n,-n\}\) for each \(n\gt0\), so \(X/G\) is countably infinite. The formula would assert \(\infty = \frac{1}{2}(\infty + 1)\), which is not a meaningful arithmetic statement, so the counting content of the lemma is lost even though both sides are "infinite".
  • Group-action axioms dropped (e.g. only a "function" \(G\times X \to X\) without \(g\cdot(h\cdot x)=(gh)\cdot x\)): stabilisers \(G_x\) need not be subgroups, Lagrange's theorem (Step 3) cannot be invoked, and \(|Gx|\) need not divide \(|G|\); the bijection in Step 3 fails and the whole derivation collapses at that step.
Common errors
  • Forgetting to include \(g = e\) in the sum \(\sum_{g\in G}|X^g|\); since \(X^e = X\), omitting it silently discards the largest term and always undercounts.
  • Computing \(|X^g|\) as the number of orbits fixed setwise by \(g\) rather than points fixed pointwise — Burnside requires pointwise fixed points (\(g\cdot x = x\)), not \(g\) mapping an orbit or subset to itself.
  • Applying the lemma to an action that is not transitive and then assuming \(|X/G|=1\) or that a single "typical" element realises the average — the average is over the whole group, and no individual \(g\) need fix exactly \(\frac{1}{|G|}\sum_g|X^g|\) points.
  • Miscounting \(|G|\) itself when \(G\) is a subgroup of a larger symmetric group (e.g. using \(|S_n|\) instead of the actual acting subgroup's order), which silently corrupts the average.
  • Double-counting fixed colourings/configurations that are related by a symmetry other than the one being summed over, conflating "fixed by \(g\)" with "fixed by some element of \(G\)".
Discussion

The result is often called the "Cauchy–Frobenius lemma" or, informally and inaccurately, "Burnside's lemma" — Burnside stated it in his 1897 book Theory of Groups of Finite Order but attributed it to Frobenius (1887), who in turn built on Cauchy's earlier work; the misattribution is now a classic instance of Stigler's law of eponymy in mathematics. Historically it predates and anticipates the character-theoretic viewpoint that would later unify it with representation theory.

The deeper conceptual reading is representation-theoretic: consider the permutation representation \(\mathbb{C}[X]\), with \(G\) acting by permuting basis vectors \(e_x\). The character of this representation is exactly \(\chi(g) = |X^g|\) (a permutation matrix has trace equal to its number of fixed basis vectors). Burnside's lemma is then precisely the formula for the multiplicity of the trivial representation inside \(\mathbb{C}[X]\), \(\langle \chi, \mathbf{1}\rangle = \frac{1}{|G|}\sum_g \chi(g)\), and this multiplicity equals the number of orbits because \(\mathbb{C}[X] \cong \bigoplus_{O \in X/G} \mathbb{C}[O]\) and each transitive permutation module \(\mathbb{C}[O]\) contains the trivial representation with multiplicity exactly one (spanned by the all-ones vector on \(O\)).

This representation-theoretic reading is what makes the lemma a genuine theorem "about" representation theory rather than a standalone combinatorial trick: it is the \(n=1\) case of the general inner-product formula \(\langle \chi_V, \chi_W\rangle = \dim \mathrm{Hom}_G(V,W)\) for characters of finite-dimensional \(G\)-representations, specialised to \(W\) trivial. Seen this way, Pólya enumeration (weighting orbits by a generating-function variable per colour) is obtained by replacing the trivial character with a suitably weighted class function, and Burnside's lemma is recovered by setting all weights to \(1\).

Common misconception: students often believe the lemma "counts symmetric objects" directly, when in fact it counts orbits (equivalence classes under symmetry) — the objects themselves are elements of \(X\), and the lemma never inspects any single object's symmetry, only aggregate fixed-point statistics across the whole group.

Worked examples
1
Colour the 4 beads of a square necklace (fixed vertices of a square, not free to flip over — rotations only) with 2 colours. Count colourings up to rotational symmetry. Here \(G = \mathbb{Z}/4 = \{e, r, r^2, r^3\}\) acting on \(X = \{2 \text{-colourings of } 4 \text{ beads}\}\), \(|X| = 2^4 = 16\).
Set up the group and the set it acts on. A
2
\[ |X^e| = 2^4 = 16 \quad(\text{every colouring is fixed by the identity}) \]
\(X^e = X\) always, since \(e\) acts trivially. A
3
\[ |X^r| = 2, \qquad |X^{r^3}| = 2, \qquad |X^{r^2}| = 2^2 = 4 \]
A colouring is fixed by \(r\) (rotate by \(90^\circ\)) exactly when all 4 beads share one colour, since \(r\) is a single 4-cycle on the beads: \(2\) choices. Likewise \(r^3\) is also a single 4-cycle (its inverse), giving \(2\). The element \(r^2\) (rotate \(180^\circ\)) is a product of two 2-cycles (bead 1 with bead 3, bead 2 with bead 4), so each cycle is independently coloured: \(2^2 = 4\) fixed colourings. (General fact used: a permutation with cycle type having \(c\) cycles fixes exactly \(k^c\) colourings with \(k\) colours, since colour must be constant on each cycle.) B
4
\[ |X/G| = \frac{1}{4}\left(16 + 2 + 4 + 2\right) = \frac{24}{4} = 6 \]
Apply Burnside's lemma directly with the four computed fixed-point counts. A
There are exactly \(6\) distinct 2-colourings of the 4 beads up to rotation.
1
Count the number of distinct ways to 3-colour the vertices of an equilateral triangle up to the full dihedral symmetry group \(D_3\) (rotations and reflections), \(|D_3| = 6\). Here \(X\) is the set of 3-colourings of the 3 vertices with 3 colours, \(|X| = 3^3 = 27\).
Set up \(G = D_3\) acting on \(X\), \(|X|=27\). A
2
\(D_3\) has cycle types on the 3 vertices: identity \(e\) (3 fixed points, 3 cycles of length 1); two non-trivial rotations \(r, r^2\) (one 3-cycle each); three reflections, each fixing 1 vertex and swapping the other two (1 cycle of length 1, 1 cycle of length 2, so 2 cycles total).
Classify all 6 elements of \(D_3\) by their cycle structure on the 3 vertices, since \(|X^g| = 3^{(\text{number of cycles of } g)}\) as in Example 1. B
3
\[ |X^e| = 3^3 = 27,\quad |X^r| = |X^{r^2}| = 3^1 = 3,\quad |X^{s_i}| = 3^2 = 9 \ (i=1,2,3) \]
Apply the cycle count from Step 2: identity has 3 cycles, each rotation has 1 cycle, each of the 3 reflections has 2 cycles. A
4
\[ |X/G| = \frac{1}{6}\left(27 + 3 + 3 + 9 + 9 + 9\right) = \frac{60}{6} = 10 \]
Sum all 6 fixed-point counts (identity, two rotations, three reflections) and divide by \(|G|=6\) per Burnside's lemma. A
There are exactly \(10\) distinct 3-colourings of a triangle's vertices up to rotation and reflection.
Problems
  1. How many ways are there to colour the 4 beads of a square necklace with 2 colours, up to the full symmetry group \(D_4\) (rotations and reflections), \(|D_4|=8\)?
    Solution Vertices of a square, \(X\) = 2-colourings, \(|X|=2^4=16\). Cycle types under \(D_4\): identity (4 cycles) gives \(2^4=16\); rotations by \(90^\circ,270^\circ\) (1 cycle each, a 4-cycle) give \(2^1=2\) each; rotation by \(180^\circ\) (2 cycles) gives \(2^2=4\); two "diagonal" reflections (fix 2 opposite vertices, swap the other 2: 2 fixed cycles + 1 swap = 3 cycles) give \(2^3=8\) each; two "edge" reflections (swap both pairs of vertices: 2 cycles) give \(2^2=4\) each. Sum: \(16 + 2 + 2 + 4 + 8 + 8 + 4 + 4 = 48\). Then \(|X/G| = 48/8 = 6\).
  2. A group \(G\) of order 12 acts on a set \(X\) of size 8, and the action has exactly 2 orbits. If \(11\) of the non-identity elements fix 0 points each and one further non-identity element fixes 4 points, is this consistent with Burnside's lemma? (There are 11 non-identity elements total in a group of order 12.)
    Solution By Burnside, \(2 = |X/G| = \frac{1}{12}\left(|X^e| + \sum_{g\neq e}|X^g|\right) = \frac{1}{12}(8 + \sum_{g\neq e}|X^g|)\), so \(\sum_{g\neq e}|X^g| = 24 - 8 = 16\). But the problem states 11 non-identity elements: if 10 of them fix 0 and one fixes 4, the sum is \(4\), not \(16\); if the wording means "each of the 11 fixes 0 except one which fixes 4", the total is still \(0\times10 + 4 = 4 \neq 16\). This is inconsistent — no such fixed-point distribution can produce exactly 2 orbits on an 8-element set under a group of order 12; the given data would instead force \(|X/G| = \frac{1}{12}(8+4) = 1\), a transitive action, not 2 orbits.
  3. Let \(G = \mathbb{Z}/n\) act on itself by left multiplication (the regular action). Verify Burnside's lemma gives the (obvious) correct number of orbits.
    Solution For \(g \neq e\) in a regular action, \(g\cdot x = x \implies x = g^{-1}x\), but left multiplication by any non-identity element has no fixed point (if \(gx=x\) then \(g=e\) by cancellation), so \(|X^g|=0\) for all \(g\neq e\), and \(|X^e|=|X|=n\). Burnside gives \(|X/G| = \frac{1}{n}(n + 0 + \cdots + 0) = 1\), matching the fact that a regular action is transitive (single orbit).
  4. Use Burnside's lemma to count binary strings of length 6 arranged in a circle (necklaces), up to rotation only (\(G=\mathbb{Z}/6\)).
    Solution \(|X|=2^6=64\). For \(g = r^k\) (rotation by \(k\) positions), the number of cycles on the 6 positions is \(\gcd(k,6)\), so \(|X^{r^k}| = 2^{\gcd(k,6)}\). \(k=0\): \(\gcd=6\), \(2^6=64\). \(k=1\): \(\gcd=1\), \(2\). \(k=2\): \(\gcd=2\), \(4\). \(k=3\): \(\gcd=3\), \(8\). \(k=4\): \(\gcd=2\), \(4\). \(k=5\): \(\gcd=1\), \(2\). Sum \(=64+2+4+8+4+2=84\). \(|X/G| = 84/6 = 14\).
  5. Explain why, for any action of a finite group \(G\) on a finite set \(X\), the quantity \(\frac{1}{|G|}\sum_{g\in G}|X^g|\) must always be a non-negative integer, using only the statement of Burnside's lemma (no re-proof needed) plus one further observation.
    Solution By Burnside's lemma, \(\frac{1}{|G|}\sum_{g\in G}|X^g|\) is equal to \(|X/G|\), the number of orbits — and \(|X/G|\) is, by definition, the cardinality of a set (the orbit set), hence automatically a non-negative integer. The equality is not merely an approximation or bound; it is exact, so the left side inherits integrality for free from the right side being a literal set size. No divisibility argument on the sum itself is needed once the identity is granted.