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 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.^[1] 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. (However a mirror reflection might give a different compound.)

Formally, 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 (left invariant by g): that is, X^g = { x ∈ X | g.x = x }. Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|:^[2]

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

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 G, there is still a bijection:

$${\displaystyle G\times X/G\ \longleftrightarrow \ \coprod _{g\in G}X^{g}.}$$