TOPICS
Search

Cauchy-Frobenius Lemma


Let J be a finite group and the image R(J) be a representation which is a homomorphism of J into a permutation group S(X), where S(X) is the group of all permutations of a set X. Define the orbits of R(J) as the equivalence classes under x∼y, which is true if there is some permutation p in R(J) such that p(x)=y. Define the fixed points of p as the elements x of X for which p(x)=x. Then the arithmetic mean number of fixed points of permutations in R(J) is equal to the number of orbits of R(J).

The lemma was apparently known by Cauchy (1845) in obscure form and Frobenius (1887) prior to Burnside's (1900) rediscovery. It is sometimes also called Burnside's lemma, the orbit-counting theorem, the Pólya-Burnside lemma, or even "the lemma that is not Burnside's!" Whatever its name, the lemma was subsequently extended and refined by Pólya (1937) for applications in combinatorial counting problems. In this form, it is known as Pólya enumeration theorem.


See also

Pólya Enumeration Theorem

Explore with Wolfram|Alpha

References

Burnside, W. "On Some Properties of Groups of Odd Order." Proc. London Math. Soc. 33, 162-184, 1900.Cauchy, A. "Mémoire sur diverses propriétés remarquables des substitutions régulières ou irrégulières, et des systémes de substitutiones conjugées." Comptes Rendus Acad. Sci. Paris 21, 835, 1845. Reprinted in Œuvres Complètes d'Augustin Cauchy, Tome IX. Paris: Gauthier-Villars, 342-360, 1896.Frobenius, F. G. "Über die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul." J. reine angew. Math. 101, 273-299, 1887. Reprinted in Ferdinand Georg Frobenius Gesammelte Abhandlungen, Band II. Berlin: Springer-Verlag, pp. 304-330, 1968.Harary, F. and Palmer, E. M. "Burnside's Lemma." §2.3 in Graphical Enumeration. New York: Academic Press, pp. 38-41, 1973.Neumann, P. M. "A Lemma that is not Burnside's." Math. Scientist 4, 133-141, 1979.Khan, M. R. "A Counting Formula for Primitive Tetrahedra in Z^3." Amer. Math. Monthly 106, 525-533, 1999.Pólya, G. "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, und chemische Verbindungen." Acta Math. 68, 145-254, 1937.Rotman, J. A First Course in Abstract Algebra, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Cite this as:

Weisstein, Eric W. "Cauchy-Frobenius Lemma." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Cauchy-FrobeniusLemma.html

Subject classifications