Namespaces
Variants
Actions

Difference between revisions of "Pólya theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (fixing superscripts)
 
(One intermediate revision by the same user not shown)
Line 33: Line 33:
 
$$  
 
$$  
 
\sum _ { F } w( F  )  = \  
 
\sum _ { F } w( F  )  = \  
P \left ( G;  \sum _ {r \in R } w( r) \dots
+
P \left ( G;  \sum _ {r \in R } w( r), \dots,
 
\sum _ {r \in R } w  ^ {n} ( r) \right ) ,
 
\sum _ {r \in R } w  ^ {n} ( r) \right ) ,
 
$$
 
$$
Line 40: Line 40:
  
 
$$  
 
$$  
P( G;  x _ {1} \dots x _ {n} )  = \  
+
P( G;  x _ {1}, \dots, x _ {n} )  = \  
| G |  ^ {-} 1 \sum _ {g \in G }  \prod _ {k= 1 } ^ { n }  
+
| G |  ^ {- 1} \sum _ {g \in G }  \prod _ {k= 1 } ^ { n }  
 
( x _ {k} ) ^ {j _ {k} ( g) }  =  P( G)
 
( x _ {k} ) ^ {j _ {k} ( g) }  =  P( G)
 
$$
 
$$
Line 54: Line 54:
  
 
If for the weights of the elements of  $  R $
 
If for the weights of the elements of  $  R $
one takes powers of an independent variable  $  x $(
+
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} $
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 $
 
is the number of elements in  $  R $
 
of weight  $  x  ^ {k} $)  
 
of weight  $  x  ^ {k} $)  
and  $  \Phi ( x) = \sum _ {k=} 0 ^  \infty  b _ {k} x  ^ {k} $(
+
and  $  \Phi ( x) = \sum _ {k= 0}  ^  \infty  b _ {k} x  ^ {k} $ (the so-called  "series that enumerates configurations" , where  $  b _ {k} $
the so-called  "series that enumerates configurations" , where  $  b _ {k} $
 
 
is the number of classes in  $  R  ^ {D} $
 
is the number of classes in  $  R  ^ {D} $
 
of weight  $  x  ^ {k} $),  
 
of weight  $  x  ^ {k} $),  
Line 67: Line 64:
 
$$  
 
$$  
 
\Phi ( x)  = \  
 
\Phi ( x)  = \  
P( G;  \phi ( x) \dots \phi ( x  ^ {n} )) .
+
P( G;  \phi ( x), \dots, \phi ( x  ^ {n} )) .
 
$$
 
$$
  
Line 75: Line 72:
 
$  w( r) \equiv 1 $,  
 
$  w( r) \equiv 1 $,  
 
then  $  \phi ( x) = m $
 
then  $  \phi ( x) = m $
and  $  P( G;  m \dots m) $
+
and  $  P( G;  m, \dots, m) $
 
is the number of equivalence classes.
 
is the number of equivalence classes.
  
Line 93: Line 90:
 
3) Let  $  R = \{ 0, 1 \} $
 
3) Let  $  R = \{ 0, 1 \} $
 
and let  $  D = V  ^ {2} $
 
and let  $  D = V  ^ {2} $
be all  $  2 $-
+
be all  $  2 $-subsets  $  \{ i, j \} $
subsets  $  \{ i, j \} $
+
of a set  $  V = \{ 1, \dots, p \} $;  
of a set  $  V = \{ 1 \dots p \} $;  
 
 
then  $  f \in R  ^ {D} $
 
then  $  f \in R  ^ {D} $
 
is a labelled graph with vertices from  $  V $
 
is a labelled graph with vertices from  $  V $
Line 111: Line 107:
 
in  $  D $
 
in  $  D $
 
by the relation  $  g _  \sigma  \{ i, j \} = \{ \sigma ( i) , \sigma ( j) \} $
 
by the relation  $  g _  \sigma  \{ i, j \} = \{ \sigma ( i) , \sigma ( j) \} $
one obtains a binary group  $  G = S  ^ {(} 2) = \{ g _  \sigma  \} $
+
one obtains a binary group  $  G = S  ^ {( 2)} = \{ g _  \sigma  \} $
acting on  $  D = V  ^ {(} 2) $.
+
acting on  $  D = V  ^ {( 2)} $.
  
For the sequence  $  g _ {pk} $(
+
For the sequence  $  g _ {pk} $ (the numbers of graphs with  $  p $
the numbers of graphs with  $  p $
 
 
vertices and  $  k $
 
vertices and  $  k $
edges),  $  k = 1, 2 \dots $
+
edges),  $  k = 1, 2, \dots $
 
Pólya's theorem gives the generating function
 
Pólya's theorem gives the generating function
  
 
$$  
 
$$  
 
g _ {p} ( x)  = \  
 
g _ {p} ( x)  = \  
\sum _ { k= } 0 ^  \infty  g _ {pk} x  ^ {k}  = \  
+
\sum _ { k= 0} ^  \infty  g _ {pk} x  ^ {k}  = \  
P( S _ {p}  ^ {(} 2) ;  1+ x).
+
P( S _ {p}  ^ {( 2)} ;  1+ x).
 
$$
 
$$
  
 
For the identity permutation group  $  E _ {n} $,  
 
For the identity permutation group  $  E _ {n} $,  
 
the symmetric permutation group  $  S _ {n} $
 
the symmetric permutation group  $  S _ {n} $
and the binary permutation group  $  S _ {n}  ^ {(} 2) $,  
+
and the binary permutation group  $  S _ {n}  ^ {( 2)} $,  
 
the cycle index has the form
 
the cycle index has the form
  
Line 136: Line 131:
  
 
$$  
 
$$  
P( S _ {n} ;  x _ {1} \dots x _ {n} )  =  \sum  ^ {*} \  
+
P( S _ {n} ;  x _ {1}, \dots, x _ {n} )  =  \sum  ^ {*} \  
\prod _ { i= } 1 ^ { n }   
+
\prod _ { i= 1} ^ { n }   
 
\frac{1}{k _ {i} ! }
 
\frac{1}{k _ {i} ! }
 
  \left (  
 
  \left (  
Line 145: Line 140:
  
 
$$  
 
$$  
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
+
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
 
$$
 
$$
  
Line 155: Line 150:
 
\end{array}
 
\end{array}
 
  \right )
 
  \right )
  } \prod _ { i= } 1 ^ { {[( } n- 1)/2] } x _ {2i+} 1 ^ {ik _ {2i} + 1 }
+
  } \prod _ { i= 1} ^ { [(  n- 1)/2] } x _ {2i+} 1 ^ {ik _ {2i} + 1 }
\prod _ { r< } 2 x _ {[} r,s] ^ {( r,s) k _ {r} k _ {s} } ,
+
\prod _ { r< 2} x _ {[ r,s]} ^ {( r,s) k _ {r} k _ {s} } ,
 
$$
 
$$
  
Line 164: Line 159:
 
and  $  s $,  
 
and  $  s $,  
 
and the summation  $  \sum  ^ {*} $
 
and the summation  $  \sum  ^ {*} $
extends over  $  k _ {1} \dots k _ {n} $
+
extends over  $  k _ {1}, \dots, k _ {n} $
 
subject to the condition  $  k _ {1} + 2k _ {2} + \dots + nk _ {n} = 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 [[#References|[4]]].
 
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 [[#References|[4]]].

Latest revision as of 09:10, 23 January 2022


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)
How to Cite This Entry:
Pólya theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=P%C3%B3lya_theorem&oldid=48358
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article