Burnside's lemma
Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy-Frobenius lemma or the orbit-counting theorem, is a result in group theory which is often useful in taking account of
symmetry when counting mathematical objects. Its various eponyms include
William Burnside, George Plya, Augustin Louis Cauchy, and
Ferdinand Georg Frobenius. Note that this result is certainly not due to Burnside himself, who merely quotes it in his book 'On the Theory of Groups of Finite Order'.
In the following, let
G be a finite group that acts on a
set X.
Encyclopedia
Burnside's lemma, sometimes also called
Burnside's counting theorem, the
Cauchy-Frobenius lemma or the
orbit-counting theorem, is a result in group theory which is often useful in taking account of
symmetry when counting mathematical objects. Its various eponyms include
William Burnside, George Pólya, Augustin Louis Cauchy, and
Ferdinand Georg Frobenius. Note that this result is certainly not due to Burnside himself, who merely quotes it in his book 'On the Theory of Groups of Finite Order'.
In the following, let
G be a finite group that acts on a
set X. For each
g in
G let
Xg denote the set of
elements in
X that are fixed by
g. Burnside's lemma asserts the following formula for the number of orbits, denoted |
X/
G|:
Thus the number of orbits is equal to the average number of points fixed by an element of
G .
Example application
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 3
6 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 the 24 elements of
G.
- one identity element fixing all 36 elements of X
- six 90-degree face rotations fixing 33 elements of X
- three 180-degree face rotations fixing 34 elements of X
- eight 120-degree vertex rotations fixing 32 elements of X
- six 180-degree edge rotations fixing 33 elements of X
A detailed examination of these automorphisms may be found
.
The average fix size is thus
-
Hence there are 57 rotationally distinct colourings of the faces of a cube in three colours.
Proof
The proof uses the orbit-stabilizer theorem and the fact that
X is the disjoint union of the orbits:
History
William Burnside stated and proved this lemma in his 1897 about this formula, but
mathematical historians have pointed out that he was not the first to discover it;
Cauchy in 1845 and Frobenius in 1887 also knew of this formula. In fact, the lemma was apparently so well known that Burnside simply omitted to attribute it to Cauchy.
