Prove Burnside’s Orbit-Counting Lemma: If a finite group \(G\) acts on a finite set \(X\), then the number of orbits \(|X/G|\) is given by: \[ |X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|, \] where \(X^g = \{x \in X \mid g \cdot x = x\}\) is the fixed point set of \(g\).
Solution
Let \[ S=\{(g,x)\in G\times X:g\cdot x=x\}. \] We count \(|S|\) in two ways.
For fixed \(g\in G\), the admissible \(x\) are exactly \(X^g\), so \[ |S|=\sum_{g\in G}|X^g|. \] For fixed \(x\in X\), the admissible \(g\) are exactly the stabilizer \(G_x\), so \[ |S|=\sum_{x\in X}|G_x|. \]
Now sum the second expression orbit by orbit. If \(\mathcal O\) is an orbit and \(x\in\mathcal O\), then orbit-stabilizer gives \[ |G_x|=\frac{|G|}{|\mathcal O|}. \] Hence \[ \sum_{x\in\mathcal O}|G_x| =|\mathcal O|\frac{|G|}{|\mathcal O|} =|G|. \] There are \(|X/G|\) orbits, so \[ \sum_{x\in X}|G_x|=|G|\,|X/G|. \] Combining the two counts yields \[ \boxed{|X/G|=\frac1{|G|}\sum_{g\in G}|X^g|}. \]