Group Actions and Burnside's Lemma

Pólya enumeration theory counts distinct objects under symmetry by combining group actions with generating functions. The starting point is Burnside's lemma, which counts orbits of a group action by averaging fixed points.

Group Actions on Sets

Definition8.1Group Action

A group action of a finite group $G$ on a finite set $X$ is a homomorphism $\phi: G \to \operatorname{Sym}(X)$ . For $g \in G$ and $x \in X$ , we write $g \cdot x = \phi(g)(x)$ . The action satisfies $e \cdot x = x$ and $(gh) \cdot x = g \cdot (h \cdot x)$ .

Definition8.2Orbit and Stabilizer

For $x \in X$ , the orbit of $x$ is $\operatorname{Orb}(x) = \{g \cdot x : g \in G\}$ and the stabilizer is $\operatorname{Stab}(x) = \{g \in G : g \cdot x = x\}$ . The orbit-stabilizer theorem states $|G| = |\operatorname{Orb}(x)| \cdot |\operatorname{Stab}(x)|$ .

Definition8.3Fixed Point Set

For $g \in G$ , the fixed point set is $\operatorname{Fix}(g) = \{x \in X : g \cdot x = x\}$ . The number of orbits of $G$ on $X$ is related to fixed points by Burnside's lemma.

Burnside's Lemma

ExampleNecklaces under Rotation

Count distinct necklaces with $n$ beads and $k$ colors under rotation (the cyclic group $C_n$ ). With $n = 4$ and $k = 2$ colors: the group $C_4 = \{e, r, r^2, r^3\}$ acts on $2^4 = 16$ colorings. Fixed points: $|\operatorname{Fix}(e)| = 16$ , $|\operatorname{Fix}(r)| = 2$ (all same color), $|\operatorname{Fix}(r^2)| = 4$ (period-2 patterns), $|\operatorname{Fix}(r^3)| = 2$ . Total: $(16 + 2 + 4 + 2)/4 = 6$ distinct necklaces.

RemarkHistorical Note

Although commonly called "Burnside's lemma," the result was known earlier to Cauchy and Frobenius. Burnside himself attributed it to Frobenius. It is sometimes called the "Cauchy-Frobenius lemma" or "the lemma that is not Burnside's."

Cycle Index

Definition8.4Cycle Index

For a permutation group $G$ acting on $[n]$ , the cycle index is the polynomial: $Z_G(x_1, x_2, \ldots, x_n) = \frac{1}{|G|} \sum_{g \in G} x_1^{c_1(g)} x_2^{c_2(g)} \cdots x_n^{c_n(g)},$ where $c_k(g)$ is the number of $k$ -cycles in the disjoint cycle decomposition of $g \in \operatorname{Sym}(n)$ . The cycle index encodes the full orbit structure of the group action.

ExampleCycle Index of $C_4$

For the cyclic group $C_4$ acting on 4 positions:

$e$ : $(1)(2)(3)(4) \to x_1^4$
$r$ : $(1234) \to x_4$
$r^2$ : $(13)(24) \to x_2^2$
$r^3$ : $(1432) \to x_4$

So $Z_{C_4} = \frac{1}{4}(x_1^4 + x_2^2 + 2x_4)$ .