Pólya theorem

Let be the set of mappings from a finite set , , into a set , and let be the permutation group for . This group generates a decomposition of into equivalence classes in which belong to the same class if and only if one can find a such that for all . Assign to each a weight that is an element of a commutative ring. The weight of is taken to be equal to and the weight of a class is defined as the weight of any . One then has

where the sum on the left is taken over all the equivalence classes and

is the cycle index of , where is the number of cycles of length of the permutation in its decomposition as a product of independent cycles.

The theorem was published in 1937 by G. Pólya [3].

If for the weights of the elements of one takes powers of an independent variable (or the product of powers of several variables), then for (the so-called "series that enumerates figures" , where is the number of elements in of weight ) and (the so-called "series that enumerates configurations" , where is the number of classes in of weight ), the following applies, according to Pólya's theorem:

Examples.

1) If , , then and is the number of equivalence classes.

2) If , , then , and with can be interpreted as a subset of of cardinality . The group defines orbits of subsets of , and the coefficient of in the polynomial is the number of orbits consisting of subsets of cardinality .

3) Let and let be all -subsets of a set ; then is a labelled graph with vertices from in which the two vertices and are adjacent if . Let ; then if , is the number of edges in the graph corresponding to the mapping . If the symmetric group acts on , then on defining for the substitution in by the relation one obtains a binary group acting on .

For the sequence (the numbers of graphs with vertices and edges), Pólya's theorem gives the generating function

For the identity permutation group , the symmetric permutation group and the binary permutation group , the cycle index has the form

respectively, where is the greatest common divisor and is the least common multiple of and , and the summation extends over subject to the condition . Cycle indices are known for alternating, cyclic and dihedral groups, as well as formulas for deriving the cycle indices for the product, the Cartesian product and the wreath product of groups [4].

There are extensions of Pólya's theorem to cases of a different definition of the weight function and equivalence classes [1].

References

[1]	N.G. de Bruijn, "Polya's theory of counting" E.F. Beckenbach (ed.) , Applied combinatorial mathematics , Wiley (1964) pp. Chapt. 5
[2]	V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[3]	G. Pólya, "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen" Acta Math. , 68 (1937) pp. 145–254
[4]	F Harary, E. Palmer, "Graphical enumeration" , Acad. Press (1973)