info prev up next book cdrom email home

Burnside's Lemma

Let $J$ be a Finite Group and the image $R(J)$ be a representation which is a Homeomorphism of $J$ into a Permutation Group $S(X)$, where $S(X)$ is the Group of all permutations of a Set $X$. Define the orbits of $R(J)$ as the equivalence classes under $x\sim y$, which is true if there is some permutation $p$ in $R(J)$ such that $p(x)=y$. Define the fixed points of $p$ as the elements $x$ of $X$ for which $p(x)=x$. Then the Average number of Fixed Points of permutations in $R(J)$ is equal to the number of orbits of $R(J)$.

The Lemma was apparently known by Cauchy (1845) in obscure form and Frobenius (1887) prior to Burnside's (1900) rediscovery. It was subsequently extended and refined by Pólya (1937) for applications in Combinatorial counting problems. In this form, it is known as Pólya Enumeration Theorem.


Pólya, G. ``Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, und chemische Verbindungen.'' Acta Math. 68, 145-254, 1937.

© 1996-9 Eric W. Weisstein