### Paper Menu >>

### Journal Menu >>

Intelligent Information Management, 2009, 1, 172-173 doi:10.4236/iim.2009.13025 Published Online December 2009 (http://www.scirp.org/journal/iim) Copyright © 2009 SciRes IIM On the Pólya Enumeration Theorem L. G. FEL Department of Civil Engineering, Technion, Haifa, Israel Email: lfel@tx.technion.ac.il Abstract: Simple formulas for the number of different cyclic and dihedral necklaces containing nj beads of the j-th color,and , are derived, using the Pólya enumeration theorem. mj Nn j m j= 1= Keywords: permutations and cyclic invariance, cycle index, Pólya enumeration theorem Among a vast number of counting problems one of the most popular is a necklace enumeration. A cyclic neck- lace is a coloring in m colors of the vertices of a regular N--gon, where two colorings are equivalent if one can be obtained from the other by a cyclic symmetry CN, e.g. colored beads are placed on a circle, and the circle may be rotated (without reflections). A basic enumeration problem is then: for given m and , how many different cyclic necklaces containing nj beads of the j-th color are there. The answer follows by an appli- cation of the Pólya's theorem [1]: the number γ (CN, nm) of different cyclic necklaces is the coefficient of in the cycle index j m jnN 1= = m n m nxx 1 1 ,=,)( 1 =)( 1 / | g m g g gN g Ng i N CxxXXg N xZ (1) where )(g denotes the Euler totient function and nm denotes a tuple . ),,( 1m nn Since γ (CN, nm) is not available in closed form in standard and advanced textbooks [2–6] we found it worthwhile to derive this number from (1). In this article we prove that ,=, ! ! = ,)( 1 =, 1= 1 | d n k k kk kPwhere kPd N nC j j j m j m m m d m N (2) and Δ denotes a great common divisor gcd n^m of the tuple nm. We denote also . ),,(= 1m mkkk Note that the term does appear only m n m nxx 1 1 once in the multinomial series expansion (MSE) of (1) with a weight m nP when , 1=g .= , 1 1 1 1 m m n m n mN nnNwhere xxnPX (3) Show that for the polynomial 1>g i N CxZ con- tributes in γ (CN, nm) if and only if . We prove that if N is divisible by g and Δ is not divisible by g then the term does not appear in MSE of (1). 1> m n m nxx 1 1 Denote , and consider MSE of (1) LgN =/ NL <<1 ,= 1 1 = 1 0 m gl m gl m L m ll i l L gxxlPX (4) where lm denotes a tuple (l1,…,lm). However MSE in (4) does not contribute in γ (CN, nm) since Δ is not divisible by g, i.e. we cannot provide such g that holds for all . Thus, we have reduced expression (1) by summing only over the divisors d of Δ, ii ngl= mi ,1,= .)( 1 =/ | dN d d i N CXd N xZ (5) Denoting ,, and considering MSE of (5) we obtain dnk jj /= m kkKdN 1 ==/ .= 1 1 1 1m n m n m m dk m dk mK dxxkPxxkPX (6) Combining (5) and (6) we arrive at (2). It is easy to extend the explicit Formula (2) to the case of dihedral necklaces where two colorings are equivalent if one can be obtained from the other by a dihedral sym- metry DN, e.g. colored beads are placed on a circle, and the circle may be rotated and reflected. Start with the cycle indices [5] L. G. FEL 173 LNifXXX LNifXX xZ xZ LL L i N C i N D 2=, 2 1 ,12=, )(= 2 2 1 2 2 1 21 (7) If we have to distinguish two different cases. 12=LN 1) There is one odd integer , while the rest of ni are even, , , m jj nan 12= i m iaL1= = ii an2= .),,,,(= , 2 1 =, 1mj m mmm N aaaawhere aPnPnD (8) 2) There is more than one odd integer , , m jj nan 12= mj1 ., 2 1 =, m N m NnCnD (9) If we have to distinguish three different cases. LN 2= 1) All integers are even, , and , , mjnn m j<, ),,(= 1m mbbb jj bn 2= i m ibL1= = wherebPbPnC nD mm q m q m N m N , 4 1 4 1 , 2 1 =, =1 (10) .1),,,,(=, ,),,1,,(=,),,,1,(= 321 32123211 m m m m m m m bbbbb bbbbbbbbbb 2) There is one pair of odd integers, , while the rest of ni are even, , = 2 , 1jj n iicn 2= m jj nc 12 2 , 1 ),,,,,,,(= , 2 1 =, 21 1mjj m mmm N cccccwhere cPnPnD (11) and mjjccccL 21 1 1= . 3) There is more than one pair of odd integers , m jjjjncn 12= 2 , 12 , 1mjj 21,1 , ., 2 1 =, m N m NnCnD (12) This paper is dedicated to the memory of Yoram Zimmels. The research was partly supported by the Kamea Fellowship. REFERENCES [1] G. Pólya, “Kombinatorische anzahlbestimmungen für Gruppen, Graphen, und chemische Verbindungen,” Acta Math., Vol. 68, pp. 145–254, 1937. [2] F. Harary and E. M. Palmer, “Graphical enumeration,” Academic Press, New York, 1973. [3] J. J. Rotman, “An introduction to the theory of groups,” Boston, Mass., Allyn and Bacon, Chapter 3, 1984. [4] G. Polya and R. C. Read, “Combinatorial enumeration of groups, graphs, and chemical compounds,” Springer, New York, 1987. [5] F. Harary, “Graph theory,” Reading, Addison-Wesley, MA, 1994. [6] A. Kerber, “Applied finite group actions,” 2nd Ed., Springer, Berlin, Chap. 3, 1999. Copyright © 2009 SciRes IIM |