Group Actions, The Burnside Counting Theorem

The Burnside Counting Theorem

Let G act on S, and let χ(a) be the number of elements in S fixed by the permutation associated with a in G. Count the number of pairs a.b, where a is in G and b is in S, and the permutation of a fixes b. Clearly this is sum χ(a). It is also the sum of the size of the stabilizer of b, for all b in S.

Every orbit contributes orbit size times stabilizer size, or |G|. Therefore the total is |G| times the number of orbits. The sum of χ(a) produces the same total.

Another form of the Burnside counting theorem lets G act on S cross S by permuting the individual components as before. The number of elements fixed by a is now χ(a)2. The sum of χ(a)2 is equal to the number of orbits times |G|, as before.

When the action is doubly transitive, every pair is mapped to every other pair, so only two orbits are present, x,x and x,y. Thus the sum of χ(a)2 = 2×|G|.