Burnside's lemma

Statement

Let a finite group $G$ act on a finite set $X$. For $g \in G$, let $X^g = \{x \in X : g \cdot x = x\}$. Then the number of orbits is $|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$.

Remarks

The proof counts the pairs $(g, x)$ with $g \cdot x = x$ in two ways, and uses $|G_x| = |G| / |G \cdot x|$. For example, the rotation group $\mathbb{Z}/4\mathbb{Z}$ of a square acts on the $2^4 = 16$ colourings of the corners with two colours. The fixed colourings number $16$, $2$, $4$ and $2$, so there are $(16 + 2 + 4 + 2)/4 = 6$ colourings up to rotation.

History

William Burnside stated and proved the lemma in his 1897 book on finite groups, and he attributed it to Frobenius, 1887. Cauchy already knew the formula in 1845. For this reason, the lemma is sometimes called "the lemma that is not Burnside's".

Explanations

L1 human

The number of orbits is the average number of points that a group element fixes. This lets you count objects up to symmetry without listing them. You count the fixed objects for each symmetry, add, and divide by the number of symmetries.