Past exam of the mathematics course of the University of Cambridge / 2017 / ia / Paper 3 / 7E / a / Solution

For a group action, the orbit of a group action of $x$ is $Gx=\{gx:g\in G\}$, and its stabilizer subgroup is $G_x=\{g:gx=x\}$. The orbit-stabilizer theorem gives $|Gx||G_x|=|G|$: the map $g{G}_x\mapsto gx$ is a well-defined bijection from stabilizer cosets to the orbit.

Within one orbit, the stabilizer subgroups are conjugate, since $G_{hx}=h{G}_x{h}^{-1}$. Their sizes are therefore equal. Summing stabilizer sizes over a single orbit gives $|Gx||G_x|=|G|$, and summing over all $n$ orbits yieldsNow count the pairs $(g,x)$ fixed by the action in two ways. Holding $x$ fixed gives $|G_x|$ choices of $g$, whereas holding $g$ fixed gives $|\mathrm{Fix}(g)|$ choices of $x$. ThusCombining the two identities proves Burnside lemma:The finiteness hypotheses justify these cardinality sums. If $X$ is empty, every sum and the orbit count are zero, so the formula still applies.