William Burnside is said to have uncovered an interesting combinatorial formula while working on group theory. The lemma can be stated as follows:
Let E be a set of objects and G a group of permutations acting on E. Two objects in E are said to be distinct if no permutation in the group maps one to the other. The number of "distinct" objects is then the average number of objects left unchanged by the transformations in G.
The result is easy to verify in a number of simple cases, such as counting dominoes (see below). But it is particularly useful when direct counting would require examining too many different cases.
From dominoes to colorings
--------------------------
In a set of dominoes, each half bears between zero and six dots. Two dominoes are not considered different if one can be obtained from the other by a 180° rotation R. There are therefore seven different dominoes with zero dots on one or both halves (which are blank), six different dominoes with one dot on one or both halves (but no blank half), and so on, down to the single domino with six dots on both halves.
