# Burnside Lemma

The famous theorem which is often referred to as "Burnside's Lemma" or "Burnside's Theorem" states that when a finite group $G$ acts on a set $\Omega$, the number $k$ of orbits is the average number of fixed points of elements of $G$, that is, $k = |G|^{-1} \sum_{g \in G} |\mathrm{Fix}(g)|$, where $\mathrm{Fix}(g) = \{ \omega \in \Omega : \omega^g = \omega \}$ and the sum is over all $g \in G$. It is widely used in applications of group theory to combinatorics; in particular, it is the basis of the theory of combinatorial enumeration invented by J.H. Redfield [a7] and G. Pólya [a6]. Proofs are to be found in many textbooks on combinatorics and many elementary books on group theory (see, for example, [a5], Chap. 9).
The name refers to William Burnside (1852–1927), not to W.S. Burnside (1839–1920). There are several lemmas and theorems in group theory and representation theory to which the name of William Burnside is correctly attached (for example: Burnside's transfer theorem; Burnside's $p^\alpha q^\beta$-theorem; Burnside's basis theorem for $p$-groups). In this case, however, it is a misattribution dating from about 1960 (see [a4], [a8]). Although the result can be traced back to some work of A.L. Cauchy in 1845, in the above form it was published in 1887 by G. Frobenius [a3]. It appears in the 1897 edition of Burnside's classic [a1] with appropriate reference to Frobenius, but in the second edition [a2] the attribution has been mysteriously dropped, and this is almost certainly one reason for later confusion. Because of its origins the theorem has been referred to as the Cauchy–Frobenius theorem and also, on rare occasions, as Not Burnside's Lemma.