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-FrobeniusThe number of orbits of a finite groupGacting on a finite setXis 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.

harald.fripertinger "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

The Cauchy-Frobenius Lemma |