Burnside's Lemma

# orbits = 1/|G| _g |X^g| — average the fixed points.

The idea

Theorem (Burnside's lemma).

Let a finite group $G$ act on a finite set $X$, and for each $g \in G$ write $X^{g}$ for the set of elements of $X$ that $g$ fixes. Then the number of orbits of the action is $\#\text{orbits} = \frac{1}{|G|}\sum_{g \in G} |X^{g}|.$

The orbits are what the lemma counts. Two elements of $X$ lie in the same orbit when some $g$ carries one to the other, so when $X$ consists of configurations and $G$ of their symmetries, an orbit is one configuration counted up to symmetry: two colorings related by a rotation lie in one orbit and count once.

The lemma replaces a hard count with an easy one. To count orbits directly, we would have to compare configurations against one another and merge those that symmetry identifies. Instead we ask one question per group element, and an easier one: how many configurations does $g$ fix? Averaging the answers over the group gives the number of orbits exactly.

Ways to work on it

• Walkthrough. Count distinct necklaces under rotation by averaging the colorings each rotation fixes.
• Proof. See why — double-count the fixed pairs (g, x), then collapse via orbit–stabilizer.
• Practice. Count n-bead k-color necklaces (small n, k) under cyclic rotation.
• Hardest. Count colorings of a solid's faces up to rotation.

Not sure where to start? Take the ten-question placement test.