### 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 jmj=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 jmjnN 1==mnmnxx 11,=,)(1=)( 1/|gmgggNgNgiNCxxXXgNxZ  (1) where )(g denotes the Euler totient function and nm denotes a tuple . ),,( 1mnn 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|dnkkkkkPwherekPdNnCjjjmjmmmdmN (2) and Δ denotes a great common divisor gcd n^m of the tuple nm. We denote also . ),,(= 1mmkkk Note that the term does appear only mnmnxx 11once in the multinomial series expansion (MSE) of (1) with a weight mnP when , 1=g.=,1111mmnmnmNnnNwherexxnPX (3) Show that for the polynomial 1>giNCxZ 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>mnmnxx 11Denote , and consider MSE of (1) LgN =/ NL <<1,= 11=10mglmglmLmllilLgxxlPX  (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=/|dNddiNCXdNxZ (5) Denoting ,, and considering MSE of (5) we obtain dnk jj /= mkkKdN1==/.= 1111mnmnmmdkmdkmKdxxkPxxkPX   (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 LNifXXXLNifXXxZxZLLLiNCiND2=,21,12=,)(=22122121 (7) If we have to distinguish two different cases. 12=LN1) There is one odd integer , while the rest of ni are even, , , mjj nan 12=imiaL1==ii an2=.),,,,(=,21=,1mjmmmmNaaaawhereaPnPnD (8) 2) There is more than one odd integer , , mjj nan 12= mj1.,21=, mNmNnCnD (9) If we have to distinguish three different cases. LN 2=1) All integers are even, , and , , mjnn mj<,),,(= 1mmbbb jj bn 2=imibL1==  wherebPbPnCnDmmqmqmNmN,4141,21=,=1  (10) .1),,,,(=,,),,1,,(=,),,,1,(=32132123211mmmmmmmbbbbbbbbbbbbbbb 2) There is one pair of odd integers, , while the rest of ni are even, , =2,1jjniicn 2=mjj nc 12 2,1),,,,,,,(=,21=,211mjjmmmmNcccccwherecPnPnD (11) and mjjccccL 2111= . 3) There is more than one pair of odd integers , mjjjjncn 12= 2,12,1mjj 21,1 , .,21=, mNmNnCnD (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