Namespaces
Variants
Actions

Difference between revisions of "Pólya theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fixing superscripts)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p0735501.png" /> be the set of mappings from a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p0735502.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p0735503.png" />, into a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p0735504.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p0735505.png" /> be the [[Permutation group|permutation group]] for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p0735506.png" />. This group generates a decomposition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p0735507.png" /> into equivalence classes in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p0735508.png" /> belong to the same class if and only if one can find a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p0735509.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355010.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355011.png" />. Assign to each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355012.png" /> a weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355013.png" /> that is an element of a commutative ring. The weight of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355014.png" /> is taken to be equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355015.png" /> and the weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355016.png" /> of a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355017.png" /> is defined as the weight of any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355018.png" />. One then has
+
<!--
 +
p0735501.png
 +
$#A+1 = 92 n = 0
 +
$#C+1 = 92 : ~/encyclopedia/old_files/data/P073/P.0703550 P\Aeolya theorem
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355019.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
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|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
 
where the sum on the left is taken over all the equivalence classes and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355020.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355021.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355022.png" /> is the number of cycles of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355023.png" /> of the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355024.png" /> in its decomposition as a product of independent cycles.
+
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 [[#References|[3]]].
 
The theorem was published in 1937 by G. Pólya [[#References|[3]]].
  
If for the weights of the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355025.png" /> one takes powers of an independent variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355026.png" /> (or the product of powers of several variables), then for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355027.png" /> (the so-called  "series that enumerates figures" , where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355028.png" /> is the number of elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355029.png" /> of weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355030.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355031.png" /> (the so-called  "series that enumerates configurations" , where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355032.png" /> is the number of classes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355033.png" /> of weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355034.png" />), the following applies, according to Pólya's theorem:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355035.png" /></td> </tr></table>
+
$$
 +
\Phi ( x)  = \
 +
P( G; \phi ( x), \dots, \phi ( x  ^ {n} )) .
 +
$$
  
 
===Examples.===
 
===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.
  
1) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355037.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355039.png" /> is the number of equivalence classes.
+
2) If $  R = \{ 0, 1 \} $,  
 
+
$  w( r) = x  ^ {r} $,  
2) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355041.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355042.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355043.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355044.png" /> can be interpreted as a subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355045.png" /> of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355046.png" />. The group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355047.png" /> defines orbits of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355048.png" />, and the coefficient of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355049.png" /> in the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355050.png" /> is the number of orbits consisting of subsets of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355051.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355052.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355053.png" /> be all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355054.png" />-subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355055.png" /> of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355056.png" />; then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355057.png" /> is a labelled graph with vertices from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355058.png" /> in which the two vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355059.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355060.png" /> are adjacent if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355061.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355062.png" />; then if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355064.png" /> is the number of edges in the graph corresponding to the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355065.png" />. If the symmetric group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355066.png" /> acts on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355067.png" />, then on defining for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355068.png" /> the substitution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355069.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355070.png" /> by the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355071.png" /> one obtains a binary group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355072.png" /> acting on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355073.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355074.png" /> (the numbers of graphs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355075.png" /> vertices and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355076.png" /> edges), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355077.png" /> Pólya's theorem gives the generating function
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355078.png" /></td> </tr></table>
+
$$
 +
g _ {p} ( x)  = \
 +
\sum _ { k= 0} ^  \infty  g _ {pk} x  ^ {k}  = \
 +
P( S _ {p}  ^ {( 2)} ;  1+ x).
 +
$$
  
For the identity permutation group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355079.png" />, the symmetric permutation group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355080.png" /> and the binary permutation group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355081.png" />, the cycle index has the form
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355082.png" /></td> </tr></table>
+
$$
 +
P( E _ {n} ; x _ {1} )  = x _ {1}  ^ {n} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355083.png" /></td> </tr></table>
+
$$
 +
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} } ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355084.png" /></td> </tr></table>
+
$$
 +
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
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355085.png" /></td> </tr></table>
+
$$
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355086.png" /> is the greatest common divisor and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355087.png" /> is the least common multiple of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355088.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355089.png" />, and the summation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355090.png" /> extends over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355091.png" /> subject to the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073550/p07355092.png" />. 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]]].
+
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 [[#References|[4]]].
  
 
There are extensions of Pólya's theorem to cases of a different definition of the weight function and equivalence classes [[#References|[1]]].
 
There are extensions of Pólya's theorem to cases of a different definition of the weight function and equivalence classes [[#References|[1]]].

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=16967
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article