Burnside's Lemma

Burnside's lemma (also known as the Cauchy-Frobenius lemma) provides an elegant formula for counting the number of distinct objects under a group of symmetries, by averaging the number of fixed points over all group elements.

Statement

Theorem8.1Burnside's Lemma

Let $G$ be a finite group acting on a finite set $X$ . The number of distinct orbits is: $|X/G| = \frac{1}{|G|} \sum_{g \in G} |\operatorname{Fix}(g)|,$ where $\operatorname{Fix}(g) = \{x \in X : g \cdot x = x\}$ .

Proof

Count the pairs $(g, x)$ with $g \cdot x = x$ in two ways: $\sum_{g \in G} |\operatorname{Fix}(g)| = \sum_{x \in X} |\operatorname{Stab}(x)|.$

By the orbit-stabilizer theorem, $|\operatorname{Stab}(x)| = |G| / |\operatorname{Orb}(x)|$ . Grouping elements by orbits: $\sum_{x \in X} \frac{|G|}{|\operatorname{Orb}(x)|} = |G| \sum_{\text{orbits } O} \sum_{x \in O} \frac{1}{|O|} = |G| \cdot (\text{number of orbits}).$

Therefore $\sum_{g \in G} |\operatorname{Fix}(g)| = |G| \cdot |X/G|$ , giving the result. $\square$

■

Applications

ExampleColoring a Cube

How many distinct ways can we color the faces of a cube with $k$ colors? The rotation group of the cube has 24 elements:

1 identity: fixes $k^6$ colorings
6 face rotations ( $\pm 90°$ ): each fixes $k^3$
3 face rotations ( $180°$ ): each fixes $k^4$
8 vertex rotations ( $\pm 120°$ ): each fixes $k^2$
6 edge rotations ( $180°$ ): each fixes $k^3$

Total: $\frac{1}{24}(k^6 + 6k^3 + 3k^4 + 8k^2 + 6k^3) = \frac{k^6 + 3k^4 + 12k^3 + 8k^2}{24}$ .

For $k = 2$ : $(64 + 48 + 96 + 32)/24 = 10$ distinct 2-colorings.

RemarkConnection to Representation Theory

Burnside's lemma can be interpreted through representation theory. The number of orbits equals the dimension of the space of $G$ -invariant functions on $X$ , which by the orthogonality relations equals $\frac{1}{|G|} \sum_g |\operatorname{Fix}(g)|$ . This viewpoint generalizes to weighted counting via characters.

ExampleBinary Strings under Rotation

The number of binary strings of length $n$ up to cyclic rotation is $\frac{1}{n}\sum_{d | n} \varphi(n/d) \cdot 2^d$ , where $\varphi$ is Euler's totient function. This follows from Burnside's lemma applied to $C_n$ acting on $\{0,1\}^n$ , noting that a rotation by $d$ positions fixes $2^{\gcd(d,n)}$ strings.