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= mj1

.,
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