Encyclopedia > Cauchy-Frobenius lemma

  Article Content

Burnside's lemma

Redirected from Cauchy-Frobenius lemma

Burnside's lemma, sometimes also called Burnside's counting theorem, Polya's formula or Cauchy-Frobenius lemma, is a result in group theory which is often useful in taking account of symmetry when counting mathematical objects.

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|:

<math>|X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g|</math>

Thus the number of orbits (a natural number or infinity) is equal to the average number of points fixed by an element of G (which consequently is also a natural number or infinity).

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 36 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.

  • 1 identity element fixing all 36 elements of X
  • 6 90 degree face rotations fixing 33 elements of X
  • 3 180 degree face rotations fixing 34 elements of X
  • 8 120 degree vertex rotations fixing 32 elements of X
  • 6 180 degree edge rotations fixing 33 elements of X
The average fix size is thus
<math> \frac{1}{24}\left(3^6+6\times 3^3 + 3 \times 3^4 + 8 \times 3^2 + 6 \times 3^3 \right) = 57 </math>
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:

<math>\sum_{g \in G}|X^g| = |\{(g,x)\in G\times X \mid g.x = x\}| = \sum_{x \in X} |G_x| </math>
<math>= \sum_{x \in X} \frac{|G|}{|Gx|}\ =\ \sum_{A\in X/G} |G|\sum_{x\in A} \frac{1}{|A|} \ = \ |G| \sum_{A\in X/G} 1</math>
<math>= |G| \cdot |X/G|\,</math>
 
History

William Burnside wrote in 1900 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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Nationalities of China

... Yao[?] (瑶族) Korean (朝鲜族) Bai[?] (白族) Hani[?] (哈尼族) Li (黎族) ...