Pólya theorem

Let $ R ^ {D} $ be the set of mappings from a finite set $ D $, $ | D | = n $, into a set $ R $, and let $ G $ be the permutation group for $ D $. This group generates a decomposition of $ R ^ {D} $ into equivalence classes in which $ f _ {1} , f _ {2} \in R ^ {D} $ belong to the same class if and only if one can find a $ g \in G $ such that $ f _ {1} ( g( d)) = f _ {2} ( d) $ for all $ d \in D $. Assign to each $ r \in R $ a weight $ w( r) $ that is an element of a commutative ring. The weight of $ f $ is taken to be equal to $ w( f ) = \prod _ {d \in D } w( f( d)) $ and the weight $ w( F ) $ of a class $ F \subset R ^ {D} $ is defined as the weight of any $ f \in F $. One then has

$$ \sum _ { F } w( F ) = \ P \left ( G; \sum _ {r \in R } w( r), \dots, \sum _ {r \in R } w ^ {n} ( r) \right ) , $$

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

$$ P( G; x _ {1}, \dots, x _ {n} ) = \ | G | ^ {- 1} \sum _ {g \in G } \prod _ {k= 1 } ^ { n } ( x _ {k} ) ^ {j _ {k} ( g) } = P( G) $$

is the cycle index of $ G $, where $ j _ {k} ( g) $ is the number of cycles of length $ k $ of the permutation $ g $ 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 $ R $ one takes powers of an independent variable $ x $ (or the product of powers of several variables), then for $ \phi ( x) = \sum _ {k= 0 } ^ \infty a _ {k} x ^ {k} $ (the so-called "series that enumerates figures" , where $ a _ {k} $ is the number of elements in $ R $ of weight $ x ^ {k} $) and $ \Phi ( x) = \sum _ {k= 0} ^ \infty b _ {k} x ^ {k} $ (the so-called "series that enumerates configurations" , where $ b _ {k} $ is the number of classes in $ R ^ {D} $ of weight $ x ^ {k} $), the following applies, according to Pólya's theorem:

$$ \Phi ( x) = \ P( G; \phi ( x), \dots, \phi ( x ^ {n} )) . $$

Examples.

1) If $ | R | = m $, $ w( r) \equiv 1 $, then $ \phi ( x) = m $ and $ P( G; m, \dots, m) $ is the number of equivalence classes.

2) If $ R = \{ 0, 1 \} $, $ w( r) = x ^ {r} $, then $ \phi ( x) = 1 + x $, and $ f \in R ^ {D} $ with $ w( f ) = x ^ {k} $ can be interpreted as a subset of $ D $ of cardinality $ k $. The group $ G $ defines orbits of subsets of $ D $, and the coefficient of $ x ^ {k} $ in the polynomial $ P( G; 1+ x) $ is the number of orbits consisting of subsets of cardinality $ k $.

3) Let $ R = \{ 0, 1 \} $ and let $ D = V ^ {2} $ be all $ 2 $-subsets $ \{ i, j \} $ of a set $ V = \{ 1, \dots, p \} $; then $ f \in R ^ {D} $ is a labelled graph with vertices from $ V $ in which the two vertices $ i $ and $ j $ are adjacent if $ f ( \{ i, j \} ) = 1 $. Let $ w( r) = x ^ {r} $; then if $ w( f ) = x ^ {k} $, $ k $ is the number of edges in the graph corresponding to the mapping $ f $. If the symmetric group $ S _ {p} $ acts on $ V $, then on defining for $ \sigma \in S _ {p} $ the substitution $ g _ \sigma $ in $ D $ by the relation $ g _ \sigma \{ i, j \} = \{ \sigma ( i) , \sigma ( j) \} $ one obtains a binary group $ G = S ^ {( 2)} = \{ g _ \sigma \} $ acting on $ D = V ^ {( 2)} $.

For the sequence $ g _ {pk} $ (the numbers of graphs with $ p $ vertices and $ k $ edges), $ k = 1, 2, \dots $ Pólya's theorem gives the generating function

$$ g _ {p} ( x) = \ \sum _ { k= 0} ^ \infty g _ {pk} x ^ {k} = \ P( S _ {p} ^ {( 2)} ; 1+ x). $$

For the identity permutation group $ E _ {n} $, the symmetric permutation group $ S _ {n} $ and the binary permutation group $ S _ {n} ^ {( 2)} $, the cycle index has the form

$$ P( E _ {n} ; x _ {1} ) = x _ {1} ^ {n} , $$

$$ P( S _ {n} ; x _ {1}, \dots, x _ {n} ) = \sum ^ {*} \ \prod _ { i= 1} ^ { n } \frac{1}{k _ {i} ! } \left ( \frac{x _ {i} }{i} \right ) ^ {k _ {i} } , $$

$$ P( S _ {n} ^ {( 2)} ) = \sum ^ {*} \left ( \prod _ { i= 1} ^ { n } k _ {i} ! i ^ {k _ {i} } \right ) ^ {- 1} \prod _ { i= 1} ^ { [ n/2]} ( x _ {i} x _ {2i} ^ {i- 1} ) ^ {k _ {2} i } \times $$

$$ \times x _ {i} ^ {i \left ( \begin{array}{c} k _ {i} \\ 2 \end{array} \right ) } \prod _ { i= 1} ^ { [( n- 1)/2] } x _ {2i+} 1 ^ {ik _ {2i} + 1 } \prod _ { r< 2} x _ {[ r,s]} ^ {( r,s) k _ {r} k _ {s} } , $$

respectively, where $ ( r, s) $ is the greatest common divisor and $ [ r, s] $ is the least common multiple of $ r $ and $ s $, and the summation $ \sum ^ {*} $ extends over $ k _ {1}, \dots, k _ {n} $ subject to the condition $ k _ {1} + 2k _ {2} + \dots + nk _ {n} = n $. 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)