Suppose you want to make a necklace by stringing together four coloured beads in a circle, choosing each bead to be black or white. How many distinct necklaces are possible?
There are ways to choose the colours of the four positions independently. But many of these arrangements are really the same necklace — once you rotate the necklace by a quarter turn, becomes , which becomes , which becomes , all of which are physically the same necklace seen from different angles. If you count these four as the same, how many genuinely distinct necklaces are there?
The answer is . Burnside’s lemma — also known as the Cauchy–Frobenius lemma — turns this kind of question into a one-line calculation. It is one of the most useful counting tools in algebraic combinatorics, and it has the curious feature that it counts equivalence classes by averaging over the symmetries rather than by enumerating the classes themselves. This article is about what the lemma says, why it works, and what it has been used for over its century and a half of service.
The statement
Let a finite group act on a finite set . (For our necklaces, is the set of colour patterns, and is the cyclic group of four rotations.) Two elements of are in the same orbit if one can be transformed into the other by some element of . The set of orbits is denoted .
For each group element , let be the set of elements of that leaves unchanged. Burnside’s lemma says:
The number of distinct orbits equals the average number of fixed points of the group elements. In words: count, for each symmetry , how many patterns look exactly the same after applying ; then average over all symmetries. The result is the number of equivalence classes.
This is a strange formula. The left-hand side is something you ultimately want to know — how many essentially different objects exist. The right-hand side counts something seemingly more obscure — how many coincidences are introduced by each symmetry. But the formula is exact, and it almost always reduces a hard combinatorial counting problem to a much easier one.
The necklace calculation
Apply this to four beads in two colours under rotation. The group has four elements: the identity, and rotations by , , and . For each one, we count the patterns it fixes.
The identity does nothing, so every pattern is fixed: .
The rotation by cycles the four bead positions . A pattern is fixed iff all four positions hold the same colour: (all black or all white).
The rotation by swaps positions and . A pattern is fixed iff positions and match, and and match: .
The rotation by is the inverse of and fixes the same patterns: .
Burnside’s lemma then gives
There are six distinct -bead necklaces, exactly as advertised. The six representatives are shown below.
The numbers in parentheses count the colourings within each orbit — the size of each equivalence class. They add up to , recovering the total. The six orbits is what Burnside’s lemma computes in one line, without enumerating the patterns.
Why the lemma is true
The proof rests on a beautiful piece of double-counting. Form the set of pairs
These are the “incidence pairs” of a group element with a point it fixes. Count in two ways.
Sum over first. For each , the number of that fixes is exactly . So .
Sum over first. For each , the number of that fix is the size of the stabiliser , the subgroup of group elements that leave alone. So .
Now invoke the orbit–stabiliser theorem: for any element in an orbit , the stabiliser has size . Substituting:
The inner sum telescopes because every term equals and there are of them per orbit. Setting the two expressions for equal yields exactly Burnside’s lemma:
Divide both sides by and you have the formula. The whole argument is essentially three lines of bookkeeping built on the orbit–stabiliser identity.
Where the lemma shines
The lemma is at its best when counting under symmetry: any time you want to count objects “up to” some group of equivalences, Burnside is usually the cleanest tool.
Necklaces and bracelets. Generalising the four-bead example, the number of distinct -bead -colour necklaces (under rotation) is a Burnside calculation involving the cyclic group . Bracelets, which can additionally be flipped, use the dihedral group and have a slightly more elaborate formula.
Polyhedron colourings. How many ways can you colour the faces of a cube with colours, counting rotations of the cube as the same colouring? The rotation group of the cube has elements; Burnside reduces the calculation to summing the fixed points of each rotation type, and the answer comes out to a clean polynomial in . The same machinery handles dodecahedra, soccer balls, dice, and arbitrary symmetric solids.
Chemistry: counting isomers. Different arrangements of atoms around a central carbon, or different decorations of a ring of atoms in a molecule, are counted using Burnside under the molecule’s symmetry group. The mathematical chemist George Pólya famously extended Burnside’s lemma into the Pólya enumeration theorem in the 1930s, providing the tools that let chemists count, say, all possible isomers of a hydrocarbon by group-theoretic accounting rather than tedious enumeration.
Magic squares and other combinatorial objects. Counting distinct configurations of any object with built-in symmetry — Latin squares, Sudoku puzzles, sand mandalas — is naturally a Burnside calculation when “distinct” means “up to the appropriate symmetry group.”
A philosophical note
The lemma has an unusual epistemological flavour. To count the number of essentially different objects, you would naïvely try to list one representative of each equivalence class. Burnside’s lemma instead has you count the fixed points of every symmetry — that is, look at the relationship between the symmetries and the structures one symmetry at a time. The number of essentially different objects then emerges as an average.
This is part of a much broader pattern in mathematics, sometimes called the principle of symmetric averaging: when you want to study things “up to symmetry,” it is often easier to average a function over the symmetry group than to pick representatives directly. The same principle appears in representation theory (averaging matrix entries over a group gives projections onto invariant subspaces), in differential geometry (averaging Riemannian metrics over a group action produces invariant metrics), and in statistics (averaging an estimator over permutations gives the symmetric estimator). Burnside’s lemma is the simplest and earliest example of this template, and learning to think in its language is one of the small intellectual rites of passage in algebraic combinatorics.
The next time you ask “how many distinct ways are there to colour, arrange, or decorate something given that certain rearrangements should count as the same,” reach for Cauchy and Frobenius’s lemma. It will turn most such questions into a finite sum that you can usually compute in a few lines.
Frequently asked
Who actually proved Burnside's lemma?
Not William Burnside, despite the name. The result was proved by Augustin-Louis Cauchy in 1845 and independently by Ferdinand Frobenius in 1887. Burnside reproduced it in his influential 1897 book on group theory without claiming originality, and credited Frobenius — but later mathematicians began calling it Burnside's lemma anyway. To avoid the historical injustice it is sometimes called the Cauchy–Frobenius lemma, or 'the lemma that is not Burnside's,' in a small bit of mathematical wordplay.
What is the precise statement?
Let a finite group G act on a finite set X. The number of orbits — equivalence classes of X under the action — equals the average number of elements of X fixed by elements of G. Symbolically: |X/G| = (1/|G|) · Σ |Fix(g)|, where the sum is over all g in G. The right-hand side counts, for each group element, how many objects it leaves unchanged; dividing by |G| averages over the group.
Why does it work?
Because every element of X belongs to exactly one orbit, and the size of that orbit times the number of group elements that fix any particular element of it equals |G| (the orbit–stabiliser theorem). Summing the relation 'orbit size times stabiliser size = |G|' over all elements and rearranging gives the lemma. The underlying observation is a clever piece of double-counting: the number of pairs (g, x) with g·x = x can be summed either over g — giving Σ |Fix(g)| — or over x — giving |G| · |X/G|. Equating the two sides is the lemma.
What is Pólya enumeration?
It is a powerful generalisation of Burnside's lemma developed by George Pólya in 1937. Instead of just counting orbits, it counts orbits weighted by some property of the objects — for example, counting necklaces by how many beads of each colour they have. The result is a polynomial generating function in which each coefficient gives the number of orbits with a specific composition. Pólya enumeration is the standard tool for problems like 'how many distinct organic molecules with formula C_n H_m are there?' and is used widely in chemistry, combinatorics, and computer-aided design.