Burnside's lemma is a theorem in group theory and combinatorics that counts objects up to symmetry. It states that the number of orbits of a finite group acting on a finite set equals the average number of elements of the set fixed by a group element. The lemma replaces the potentially difficult task of identifying all symmetry classes with a collection of fixed-point counts.
Statement
Let a finite group act on a finite set . For each , define its fixed-point set by
The orbit of is
Orbits are the equivalence classes under the relation that two elements are equivalent when some group element carries one to the other. Write for the set of orbits, and use vertical bars to denote the cardinality of a finite set.
Burnside's lemma states that
Thus, although individual fixed-point counts may vary considerably, their average is always a nonnegative integer.
In counting problems, is usually a set of labeled configurations, while consists of the symmetries that are to be ignored. An orbit then represents one configuration “up to symmetry.”
Proof by double counting
Consider the set
Counting these pairs first by their group coordinate gives
For each , its stabilizer is the subgroup
Counting the same pairs by their set coordinate gives
The orbit–stabilizer theorem states that
Consequently, for any orbit , each has stabilizer size , so
Every orbit therefore contributes exactly to the sum. It follows that
which proves the formula.
This argument also explains why simply dividing by generally fails: objects with different amounts of symmetry have orbits of different sizes.
Example: coloring the vertices of a square
Suppose each vertex of a square is colored black or white. There are colorings before identifying any symmetries.
Rotations only
Take to be the four rotations of the square.
| Rotation | Condition for a coloring to be fixed | Fixed colorings |
|---|---|---|
| No restriction | ||
| All four vertices have the same color | ||
| Opposite vertices have the same color | ||
| All four vertices have the same color |
Burnside's lemma gives
colorings up to rotation.
The six classes are represented by an all-white square, an all-black square, one black vertex, one white vertex, two adjacent black vertices, and two opposite black vertices.
Rotations and reflections
If mirror images are also identified, the acting group is the dihedral group of the square, of order eight.
There are four additional symmetries:
- Two reflections through opposite vertices. Each fixes two vertices and exchanges the other two, so each fixes colorings.
- Two reflections through midpoints of opposite edges. Each exchanges two pairs of vertices, so each fixes colorings.
The number of classes becomes
The equality with the rotation-only count is particular to this example: every reflected binary coloring of the square is already rotation-equivalent to the original. With three available colors, the corresponding counts are under rotations and under rotations and reflections.
Counting colorings through permutation cycles
A common application begins with a finite set of positions on which acts. A coloring with distinguishable colors is a function
The group acts on colorings by
Each group element induces a permutation of . If this permutation has cycles, including cycles of length one, then a coloring is fixed precisely when it is constant on each cycle. Each cycle can independently receive any of the colors, giving
Hence
For example, consider positions arranged on a circle, identifying colorings under rotations but not reflections. Rotation by positions has cycles, where denotes the greatest common divisor. The number of such necklaces is therefore
with .
This counts all necklaces, including those whose color patterns repeat after fewer than positions.
Relation to Pólya enumeration
Burnside's lemma underlies Pólya's enumeration theorem, which records more detailed information about colorings.
If is the number of cycles of length in the permutation induced by , the cycle index of the action is the polynomial
Only finitely many factors occur for a finite position set.
Substituting for every recovers the ordinary coloring count. More informative substitutions produce a generating function that records how many positions receive each color. For colors represented by variables , the substitution
yields coefficients counting symmetry classes with specified color multiplicities.
Probabilistic and linear-algebraic interpretations
If is selected uniformly from , then Burnside's lemma can be written using expected value as
This averages over group elements, not over objects or orbits.
There is also an interpretation in representation theory. Form a real vector space with basis . Each group element acts by a permutation matrix , whose trace is
The averaging operator
is a projection onto the subspace of invariant vectors. That subspace has one basis vector for each orbit, obtained by summing the basis elements belonging to that orbit. Thus its dimension, and therefore the trace of , is . Taking traces gives Burnside's formula.
Applications and limitations
The lemma is used to count necklaces, bracelets, arrangements on polygons and polyhedra, unlabeled structures, and other configurations whose descriptions contain redundant labels. In graph theory, for example, the symmetric group on a vertex set acts on labeled graphs by relabeling vertices; its orbits are graph isomorphism classes.
Correct application requires specifying both the objects and their allowed symmetries:
- Rotations and reflections give different equivalence relations. Neither should be included unless the counting problem identifies configurations related by it.
- Permuting positions does not automatically permute colors. Identifying color names requires an additional action.
- Constraints must be preserved by the action. If only configurations satisfying a restriction are allowed, the chosen group must map valid configurations to valid configurations.
- Fixed-point counts remain the main computational task. Averaging is simple, but determining which objects a symmetry fixes can be difficult.
If the action is free, meaning that only the identity fixes any element, the formula reduces to
The general lemma accounts for the nontrivial stabilizers that prevent this division rule from working in other cases.
The standard numerical formula assumes that both and are finite. Infinite actions require additional hypotheses or different formulations; ordinary finite averaging cannot simply be applied unchanged.
Historical attribution
The lemma is named after William Burnside, who included it in his 1897 book Theory of Groups of Finite Order. The result predates that publication: it appeared in work of Augustin-Louis Cauchy and Ferdinand Georg Frobenius. The alternative name Cauchy–Frobenius lemma reflects that earlier history, while orbit-counting lemma describes its mathematical content.