Burnside's lemma

The first step in the proof of the lemma is to re-express the sum over the group elements g ∈ G as an equivalent sum over the set of elements x ∈ X:

${\displaystyle \sum _{g\in G}|X^{g}|=|\{(g,x)\in G\times X\mid g\cdot x=x\}|=\sum _{x\in X}|G_{x}|.}$

(Here X^g = {x ∈ X | g.x = x} is the subset of all points of X fixed by g ∈ G, whereas G_x = {g ∈ G | g.x = x} is the stabilizer subgroup of G that fixes the point x ∈ X.)

The orbit-stabilizer theorem says that there is a natural bijection for each x ∈ X between the orbit of x, G·x = {g·x | g ∈ G} ⊆ X, and the set of left cosets G/G_x of its stabilizer subgroup G_x. With Lagrange's theorem this implies

${\displaystyle |G\cdot x|=[G\,:\,G_{x}]=|G|/|G_{x}|.}$

Our sum over the set X may therefore be rewritten as

${\displaystyle \sum _{x\in X}|G_{x}|=\sum _{x\in X}{\frac {|G|}{|G\cdot x|}}=|G|\sum _{x\in X}{\frac {1}{|G\cdot x|}}.}$

Finally, notice that X is the disjoint union of all its orbits in X/G, which means the sum over X may be broken up into separate sums over each individual orbit.

${\displaystyle \sum _{x\in X}{\frac {1}{|G\cdot x|}}=\sum _{A\in X/G}\sum _{x\in A}{\frac {1}{|A|}}=\sum _{A\in X/G}1=|X/G|.}$

Putting everything together gives the desired result:

${\displaystyle \sum _{g\in G}|X^{g}|=|G|\cdot |X/G|.}$

This proof is essentially also the proof of the class equation formula, simply by taking the action of G on itself (X = G) to be by conjugation, g.x = gxg⁻¹, in which case G_x instantiates to the centralizer of x in G.

Burnside's Lemma counts distinct objects, but it doesn't generate them. In general, combinatorial generation with isomorph rejection considers the same |G| actions, g, on the same |X| objects, x. But instead of checking that g.x=x, it checks that g.x has not already been generated. One way to accomplish this is by checking that g.x is not lexicographically less than x, using the lexicographically least member of each equivalence class as the class representative.[3] Counting the objects generated with an isomorph-rejection technique such as this provides a way of checking that Burnside's Lemma was correctly applied.

William Burnside stated and proved this lemma, attributing it to Frobenius 1887, in his 1897 book on finite groups. But, even prior to Frobenius, the formula was known to Cauchy in 1845. In fact, the lemma was apparently so well known that Burnside simply omitted to attribute it to Cauchy. Consequently, this lemma is sometimes referred to as a lemma that is not Burnside's[4] Misnaming lemmas and theorems is referred to as Stigler's law of eponymy.

• Pólya enumeration theorem
• Cycle index

• Burnside, William (1897). Theory of Groups of Finite Order. Cambridge University Press – via Project Gutenberg. Also available here at Archive.org. (This is the first edition; the introduction to the second edition contains Burnside's famous volte face regarding the utility of representation theory.)
• Frobenius, Ferdinand Georg (1887), "Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul", Crelle's Journal, 101 (4): 273–299, doi:10.3931/e-rara-18804.
• Cheng, Yuanyou (1986). "A generalization of Burnside's lemma to multiply transitive groups". Journal of Hubei University of Technology. ISSN 1003-4684..
• Rotman, Joseph (1995), An introduction to the theory of groups, Springer-Verlag, ISBN 0-387-94285-8.