Burnside's lemma

In the following, let $G$ be a finite group that acts on a set $X$. For each g in G let $X^{g}$ denote the set of elements in $X$ that are fixed by $g$.

In 1900 Burnside discovered a formula for the number of orbits, denoted $|X/G|$

$|X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|$

thus the number of orbits (a natural number) is equal to the average number of points fixed by an element of $G$ (which then, corrolarily, also is a natural number). This result is also called Burnside's counting theorem, or sometimes Polya's formula, and is useful in taking account of symmetry when counting mathematical objects.

For example, the number of rotationally distinct colourings of the faces of a cube using three colours can be determined from this formula as follows.

Let X be the set of fixed coloured cubes, and let the rotation group G of the cube act on X in the natural manner. Then two elements of X belong to the same orbit precisely when one is simply a rotation of the other. The number of rotationally distinct colourings is thus the same as the number of orbits and can be found by counting the sizes of the fixed sets for elements of G.

Mathematical historians have pointed out that Burnside was not the first to discover this; Cauchy in 1845 and Frobenius in 1887 also knew this formula. - Thus it is also known as the Cauchy-Frobenius Lemma.