TOPICS
Search

Pólya Enumeration Theorem


The Pólya enumeration theorem is 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 n nodes, tournaments on n nodes, trees and rooted trees with n branches, groups of order n, etc. The theorem is an extension of the Cauchy-Frobenius lemma.

Pólya enumeration is implemented as OrbitInventory[ci, x, w] in the Wolfram Language package Combinatorica` .


See also

Cauchy-Frobenius Lemma, Cycle Index, Group, Polyhedron Coloring, Rooted Tree, Simple Graph, Tournament, Tree

Explore with Wolfram|Alpha

References

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.

Cite this as:

Weisstein, Eric W. "Pólya Enumeration Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PolyaEnumerationTheorem.html

Subject classifications