Pólya enumeration theorem

:"Enumeration theorem" redirects here. For its labelled counterpart, see Labelled enumeration theorem."

The Pólya enumeration theorem (PET), also known as Redfield–Pólya's Theorem, is a theorem in combinatorics, generalizing Burnside's lemma about number of orbits. This theorem was first discovered and published by John Howard Redfield in 1927 but its importance was overlooked and Redfield's publication was not noticed by most of mathematical community. Independently the same result was proved in 1937 by George Pólya, who also demonstrated a number of its applications, in particular to enumeration of chemical compounds.

The PET gave rise to symbolic operators and symbolic methods in enumerative combinatorics and was generalized to the fundamental theorem of combinatorial enumeration.

Informal PET statement

Suppose you have a set of "n" slots and a set of objects being distributed into these slots and a generating function "f"("a", "b", ...) of the objects by weight. Furthermore there is a permutation group "A" acting on the slots that creates equivalence classes of filled slot configurations (two configurations are equivalent if one may be obtained from the other by a permutation from "A"). Then the generating function of the equivalence classes by weight, where the weight of a configuration is the sum of the weights of the objects in the slots, is obtained by evaluating the cycle index "Z"("A") of "A" i.e.:$Z(A)(t\_1,\; t\_2,\; ldots,\; t\_n)\; =\; frac\{1\}\; sum\_\{gin\; A\}\; |mbox\{Fix\}\_omega(g)$
= frac{1}, c^, c^, ldots)or:$f(a,\; b,\; c,\; ldots)^\{j\_1(g)\}\; f(a^2,\; b^2,\; c^2,\; ldots)^\{j\_2(g)\}\; cdots\; f(a^n,\; b^n,\; c^n)^\{j\_n(g)\}.$

Substituting this for $sum\_\{omega\}\; omega\; |mbox\{Fix\}\_omega(g)|,$ in the sum over all "g" yields the substituted cycle index as claimed.

Notes

References

* cite journal
last = Redfield
first = J. Howard
title = The Theory of Group-Reduced Distributions
journal = American Journal of Mathematics
volume = 49
year = 1927
issue = 3
pages = 433–455
url = http://links.jstor.org/sici?sici=0002-9327%28192707%2949%3A3%3C433%3ATTOGD%3E2.0.CO%3B2-D
doi = 10.2307/2370675
id = MathSciNet | id = 1506633
* cite journal
author = Frank Harary
coauthors = Ed Palmer
title = The Enumeration Methods of Redfield
journal = American Journal of Mathematics
volume = 89
year = 1967
issue = 2
pages = 373–384
url = http://links.jstor.org/sici?sici=0002-9327%28196704%2989%3A2%3C373%3ATEMOR%3E2.0.CO%3B2-A
doi = 10.2307/2373127
id = MathSciNet | id = 0214487
* cite journal
author = G. Pólya
title = Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
journal = Acta Mathematica
volume = 68
year = 1937
issue = 1
pages = 145–254
url = http://www.springerlink.com/content/9021012252111875/
doi = 10.1007/BF02546665
*cite book
author = G. Pólya
coauthors = R. C. Read
title = Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds
publisher = Springer-Verlag
location = New York
date = 1987
isbn = 0-387-96413-4
id = MathSciNet | id = 0884155

External links

* [http://demonstrations.wolfram.com/ApplyingThePolyaBurnsideEnumerationTheorem/ Applying the Pólya-Burnside Enumeration Theorem] by Hector Zenil and Oleksandr Pavlyk, The Wolfram Demonstrations Project.
*
* Frederic Chyzak [http://algo.inria.fr/libraries/autocomb/Polya-html/Polya.html Enumerating alcohols and other classes of chemical moleculs, an example of Polya theory] .