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 that is often useful in taking account of symmetry when counting mathematical objects. It was discovered by Augustin Louis Cauchy and Ferdinand Georg Frobenius, and became well known after William Burnside quoted it. The result enumerates orbits of a symmetry group acting on some objects: that is, it counts distinct objects, considering objects symmetric to each other as the same; or counting distinct objects up to a symmetry equivalence relation; or counting only objects in canonical form. For example, in describing possible organic compounds of certain type, one considers them up to spatial rotation symmetry: different rotated drawings of a given molecule are chemically identical (whereas a mirror reflection might give a different compound).

Statement

Let <math>G</math> be a finite group that acts on a set <math>X</math>. For each <math>g</math> in <math>G</math>, let <math>X^g</math> denote the set of elements in <math>X</math> that are fixed by <math>g</math> (left invariant by <math>g</math>): that is, <math>X^g = \{ x \in X : g\cdot x = x\}.</math> Burnside's lemma asserts the following formula for the number of orbits, denoted <math>|X/G|</math>:

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

Thus the number of orbits (a natural number or +∞) is equal to the average number of points fixed by an element of G. For an infinite group <math>G</math>, there is still a bijection:

<math display="block">G \times X/G \ \longleftrightarrow\ \coprod_{g \in G} X^g . </math>

Examples

Necklaces

There are 8 possible bit strings of length 3, but tying together the string ends gives only four distinct 2-colored necklaces of length 3, given by the canonical forms 000, 001, 011, 111: the other strings 100 and 010 are equivalent to 001 by rotation, while 110 and 101 are equivalent to 011. That is, rotation equivalence splits the set <math>X</math> of strings into four orbits: <math display="block">X = \