info prev up next book cdrom email home

Pólya Enumeration Theorem

A very general theorem which 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 Graphs of $n$ nodes, Trees and Rooted Trees with $n$ branches, Groups of order $n$, etc. The theorem is an extension of Burnside's Lemma and is sometimes also called the Pólya-Burnside Lemma.

See also Burnside's Lemma, Graph (Graph Theory), Group, Rooted Tree, Tree


Harary, F. ``The Number of Linear, Directed, Rooted, and Connected Graphs.'' Trans. Amer. Math. Soc. 78, 445-463, 1955.

Pólya, G. ``Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, und chemische Verbindungen.'' Acta Math. 68, 145-254, 1937.

© 1996-9 Eric W. Weisstein