A very general theorem that allows the number of discrete combinatorial objects of a given type to be enumerated (counted) as a function of their "order."
The most common application is in the counting of the number of simple
graphs of
nodes, tournaments on nodes, trees and rooted
trees with
branches, groups of order , etc. The theorem is an extension of the Cauchy-Frobenius
lemma, which is sometimes also called Burnside's lemma, the Pólya-Burnside
lemma, the Cauchy-Frobenius lemma, or even "the lemma that is not Burnside's!"
Harary, F. "The Number of Linear, Directed, Rooted, and Connected Graphs." Trans. Amer. Math. Soc.78, 445-463, 1955.Harary,
F. "Pólya's Enumeration Theorem." Graph
Theory. Reading, MA: Addison-Wesley, pp. 180-184, 1994.Harary,
F. and Palmer, E. M. "Pólya's Theorem." Ch. 2 in Graphical
Enumeration. New York: Academic Press, pp. 33-50, 1973.Pólya,
G. "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, und chemische
Verbindungen." Acta Math.68, 145-254, 1937.Roberts,
F. S. Applied
Combinatorics. Englewood Cliffs, NJ: Prentice-Hall, 1984.Skiena,
S. "Polya's Theory of Counting." §1.2.6 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 25-26, 1990.Tucker, A. Applied
Combinatorics, 3rd ed. New York: Wiley, 1995.