The Cauchy-Frobenius Lemma

The Cauchy-Frobenius Lemma

The previous result is very important, it is essential in the proof of the following counting lemma which, together with later refinements, forms the basic tool of the theory of enumeration under finite group action:

The Lemma of Cauchy-Frobenius The number of orbits of a finite group G acting on a finite set X is equal to the average number of fixed points:

| G \\X | =(1)/( | G | ) å_{g ÎG} | X_g | .

Proof:

å_{g ÎG} | X_g | = å_g å_{x ÎXg} 1 = å_x å_{g ÎGx} 1 = å_x | G_x | ,

which is, by the index formula, equal to | G | å_x | G(x) | ^-1 = | G | · | G \\X | .

Now you can try to make some calculations using the Cauchy-Frobenius Lemma.

The Cauchy-Frobenius Lemma