A Study of P?olya?s Enumeration Theorem
Except where reference is made to the work of others, the work described in this thesis
is my own or was done in collaboration with my advisory committee. This thesis does
not include proprietary or classifled information.
Elizabeth C. Williams
Certiflcate of Approval:
Greg A. Harris
Associate Professor
Department of Mathematics and
Statistics
Edward E. Slaminka, Chair
Associate Professor
Department of Mathematics and
Statistics
Stewart L. Baldwin
Professor
Department of Mathematics and
Statistics
Stephen L. McFarland
Dean
Graduate School
A Study of P?olya?s Enumeration Theorem
Elizabeth C. Williams
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
August 8, 2005
A Study of P?olya?s Enumeration Theorem
Elizabeth C. Williams
Permission is granted to Auburn University to make copies of this thesis at its discretion,
upon the request of individuals or institutions and at their expense. The author reserves
all publication rights.
Signature of Author
Date
Copy sent to:
Name Date
iii
Vita
Elizabeth Craig Williams, daughter of Kenneth Neal and Jane (Thompson) Williams
was born on April 20, 1976 in Montgomery, Alabama. She is a 1994 graduate of the
Lanier High School Academic Motivational Program. She entered LaGrange College,
LaGrange, Georgia in the fall of that year and graduated with a Bachelor of Science
degree in Mathematics on 6 June, 1998. In September, 1998 she entered the Graduate
School of Auburn University as a Graduate Assistant in Mathematics.
iv
Thesis Abstract
A Study of P?olya?s Enumeration Theorem
Elizabeth C. Williams
Master of Science, August 8, 2005
(B.S., LaGrange College, 1998)
22 Typed Pages
Directed by Edward E. Slaminka
The controversial lemma, known most commonly as Burnside?s Lemma, is stated
and proven. The in uential P?olya?s Enumeration Theorem is stated and proven. Com-
putations using P?olya?s Enumeration Theorem are discussed and examples of these com-
putations are given.
v
Acknowledgments
The author would like to thank her hard-working, ?uber-understanding advisor Dr.
Edward Slaminka for helping her flnally flnd a topic to keep her interest { math and
jewelry. For his patience, knowledge and advice she will forever be indebted.
For their unconditional love and unscripted entertainment, the author acknowledges
her dogs. Who knew tossing an empty water bottle could provide mathematical inspi-
ration? Thank you for a life full of love and laughter.
The author thanks her parents for raising her in an academic environment and
teaching her to never shy from learning. Their encouragement, understanding and sup-
port (in all forms) has made her life better than most, and for that she will be inflnitely
thankful. You are my role models as a couple, as parents, as educators and as humans.
Finally, the author wishes to acknowledge her late grandfather Dr. Ernest Williams
for nurturing her imagination and for leaving a legacy of which she is extremely proud.
vi
Style manual or journal used Transactions of the American Mathematical Society
(together with the style known as \auphd"). Bibliograpy follows van Leunen?s A
Handbook for Scholars.
Computer software used The document preparation package TEX (speciflcally
LATEX) together with the departmental style-flle auphd.sty.
vii
Table of Contents
1 Introduction 1
2 Definitions and Notation 3
3 P?olya?s Enumeration Theorem 5
4 Applications of P?olya?s Enumeration Theorem 8
Bibliography 14
viii
Chapter 1
Introduction
Consider a necklace that consists of n colored beads. On paper this can be repre-
sented as a word of length n over an alphabet of k colors. For example, one such necklace
could be represented as the word bbgbrr (b for blue, g for green and r for red). Now, two
words that difier purely by a cyclic rotation must represent the same necklace and thus
are equivalent. For our above example, bbgbrr, rbbgbr, rrbbgb, brrbbg, gbrrbb and bgbrrb
are all equivalent. So, an (n;k)-necklace is an equivalence class of words of length n over
an alphabet of size k under rotation and re ection.
This raises a commonly-known enumeration question: For a given n and k, how
many unique (n;k)-necklaces can be made [1]? On a broader scale the question becomes,
\How many orbits does the dihedral group Dn have on the set of all necklaces with n-
beads over k-colors?"
Published in 1934, Georg P?olya?s Enumeration Theorem answers the complete ques-
tion of how many necklaces can be formed using n beads of k colors, accounting for sym-
metry of rotation and of re ection. Having applications in Combinatorics and Chemistry,
P?olya?s Enumeration Theorem has led to a new branch of Graph Theory, Enumerative
Graph Theory.
This theorem is stated as: Let A and B be flnite sets and let the flnite group G act
on A. Let ck(G) denote the number of permutations in G that have exactly k cycles in
their cycle decomposition on A. Then the number of orbits of G on the set BA of all
mappings f : A ! B is 1jGj
1X
k=1
ck(G)?jBjk [3].
1
Chapter two deflnes the terms and notations that will be used in the paper. Chapter
three presents and proves LaGrange?s Theorem, Burnside?s Lemma and other theorems
used in the process of proving the main theorem, which is found at the end of the chapter.
Chapter four provides several examples of applications of P?olya?s Enumeration Theorem.
2
Chapter 2
Definitions and Notation
Deflnition: Given any set X, a bijection from X to itself is a permutation.
Deflnition: For a flnite set X, jXj is the number of elements of X.
Deflnition: Sn is the set whose elements are permutations of the set of positive integers
f1;2;:::;ng
Deflnition: Symmetry refers to a rigid motion of a geometric flgure. In this paper, we
will speciflcally look at how rotations and re ections afiect vertices of geometric flgures.
Any symmetry determines a permutation in Sn by specifying where each vertex goes
under the symmetry.
Deflnition: A dihedral group, Dn, is the group of symmetries of the regular n-gon.
Deflnition: For a subgroup, H, of a group G, the number of distinct left cosets of H
in G is the index of H in G. It is written as jG : Hj.
Deflnition: A partition of a set S is a decomposition of S into nonempty disjoint subsets
such that every element of S is in exactly one of the subsets. The subsets of a partition
are called cells of the partition.
Deflnition: Each cell in the natural partition arising from an equivalence relation is an
equivalence class.
Deflnition: Let X be a set and G a group. An action of G on X is a map ` : G?X ! X
(where `(g;x) is denoted by gx) such that:
1. ex = x for all x 2 X
2.(g1g2)(x) = g1(g2x) for all x 2 X and all g1;g2 2 G.
3
Deflnition: Let X be a set, let x be an element of X and let G be any subgroup of
Dn. Then the set of all elements of G which flx x is a subgroup of G and is called the
stabilizer of x in G, denoted by Gx = fg 2 Gjgx = xg.
Deflnition: Let X be a set, let x be an element of X and let G be any subgroup of Dn.
Then the set of all elements x which remain flxed by an element of G is the set of flxed
points of g in X and is denoted by Xg = fx 2 Xjgx = xg.
Deflnition: Let  be a permutation of a set A. The orbits of  are the equivalence
classes in A determined by the following equivalence relation: For a;b 2 A, let a ? b if
and only if b =  n(a) for some n 2f1;2;3;:::g. Another way of stating this deflnition is:
Given x 2 X, the orbit of x in G, Orb(x), is the set of all images y mapped to by some
` in G. Orb(x) = fy 2 Xj`(x) = y for ` 2 Gg.
4
Chapter 3
P?olya?s Enumeration Theorem
Theorem 3.1 Let H be a subgroup of a group G. Left cosets of H form a partition of
G.
Proof: Let aH and bH be two left cosets in H. Suppose that aH and bH have at
least one element in common, say c 2 aH \ bH. Then for some h1;h2 2 H, c =
ah1 and c = bh2. Thus, ah1 = c = bh2 ) ah1 = bh2 ) a = bh2h?11 . Since H is a
subgroup, h2h?11 must be in H. Let h3 = h2h?11 2 H. Thus, a = bh3 and for every
h 2 H, ah = bh3h = bh4 for h3 ? h = h4 2 H. Therefore ah 2 bH for all h 2 H
and aH  bH. The opposite containment, bH  aH, can be shown using a similar
argument. If ah  bH and bH  aH then aH = bH, proving that two left cosets that
are not disjoint must be equal . Thus, distinct left cosets of H separate elements of G
into disjoint subsets.
Theorem 3.2 (LaGrange?s Theorem) If G is a flnite group and H is a subgroup of G,
then jGj = jHj?jG : Hj
Proof: Let G be a flnite group of order n. Let H be a subgroup of G with order k.
By Theorem 3.1, the left cosets of H separate the elements of G into mutually disjoint
subsets. Let m = jG : Hj = the number of distinct left cosets of H in G. Let aH be any
left coset of H. A mapping ` : H ! aH deflned by `(h) = ah, for h 2 H, is injective
because the cancellation law holds for G. It is also surjective since any x 2 aH can
be written as x = ah, h 2 H. Thus ` is bijective and jaHj = jHj = k. So, we have
5
the n elements of G divided into m disjoint subsets, each with k elements. Therefore
n = km )jGj = jHj?jG : Hj.
Theorem 3.3 Let G be a subgroup of Dn which acts on a flnite set X and let x 2 X.
Then jOrb(x)j=jG : Gxj= jGjjG
xj
.
Proof: By LaGrange?s Theorem, jG : Gxj = jGjjG
xj
. To show that this is the same as
jOrb(x)j, we construct a bijection ` : Orb(x) ! GG
x
deflned by `(y)=fg 2 Gjy = gxg.
Now, `(y) is not empty because if y 2 Orb(x) then there must be at least one g 2 G
such that y = gx. Choose an element, g0 2 G, such that y = g0x. Let g0h 2 g0Gx (recall
that h 2 Gx means hx = x). So g0hx = g0x = y ) g0h 2 `(y), by the deflnition of `.
Now, for the opposite inclusion, let g 2 `(y). Then y = gx; however, since y = g0x, we
have that gx = g0x ) g?10 gx = x. Thus, g?10 g 2 Gx ) g 2 g0Gx and `(y) is well-deflned
in GG
x
. Suppose that y1;y2 2 Orb(x) such that y1 6= y2. Then `(y1) = fg 2 Gjgx = y1g
and `(y2) = fg 2 Gjgx = y2g. Clearly these two sets are disjoint. Thus ` is one-to-one.
Take any coset gGx 2 GG
x
. Then gGx = `(gx). Thus ` is onto. Therefore the mapping
` : Orb(x) ! GG
x
is bijective and jOrb(x)j = jG : Gxj = jGjjG
xj
.
Theorem 3.4 The number of orbits of an action of the group G on an element x 2 X
is equal to X
x2X
1
jOrb(x)j
Proof: Since X is a disjoint union of orbits, terms in the sum can be collected as
X
x2X
1
jOrb(x)j =
NX
i=1
0
@ X
x2Orb(xi)
1
jOrb(xi)j
1
A =
NX
i=1
(1) = N.
Theorem 3.5 (Burnside?s Lemma) Let the flnite group G act on a flnite set X. Then
the number of orbits is 1jGj X
g2G
jXgj.
6
Proof: Let S = f(g;x) 2 G?Xjgx = xg. So, jSj=X
g2G
jfx 2 Xjgx = xgj = X
g2G
jXgj and
jSj = X
x2X
jfg 2 Gjgx = xgj = X
x2X
jGxj. By Theorem 3.3, jOrb(x)j = jG : Gxj = jGjjG
xj
,
so jGxj = jGjjOrb(x)j. Thus, X
g2G
jXgj = jSj = X
x2X
jGxj = X
x2X
jGj
jOrb(x)j. Divide by jGj
to get 1jGj X
g2G
jXgj = X
x2X
1
jOrb(x)j. By Theorem 3.4,
X
x2X
1
jOrb(x)j = N. Therefore,
1
jGj
X
g2G
jXgj = N.
Theorem 3.6 (P?olya?s Enumeration Theorem) Let A and B be flnite sets and let the
flnite group G act on A. Let ck(G) denote the number of permutations in G that have
exactly k cycles in their cycle decomposition on A. Then the number of orbits of G on
the set BA of all mappings f : A ! B is 1jGj
1X
k=1
ck(G)?jBjk.
Proof: From Theorem 3.5, the number of orbits is given by N = 1jGj X
g2G
jXgj. Let jXgj
denote the number of mappings, f, left flxed by a permutation g 2 G. This holds true
if and only if f is constant on each of the cycles of g. These mappings are obtained by
assigning an element of B to each cycle of g. If g has k cycles, then jBjk is the number
of mappings flxed by g.
7
Chapter 4
Applications of P?olya?s Enumeration Theorem
P?olya?s Enumeration Theorem (restated) The number of orbits of a flnite set G on
the set BA of all mappings f : A ! B is 1jGj
1X
k=1
ck(G)?jBjk.
Let A be a flnite set denoting the vertices of an n-gon, or the possible positions of
beads on a necklace.
Let B be the flnite set of colors available.
Let G be the appropriate dihedral group: D3;D4;D5 or D6.
D3 = f?0;?1;?2;?1;?2;?3g where ?i corresponds to rotating the triangle clockwise
2?i
3 radians and ?i corresponds to re ecting the triangle about the three angle bisectors.
D4 = f?0;?1;?2;?3;?1;?2;?1;?2g where ?i corresponds to rotating the square clock-
wise ?i2 radians; ?i corresponds to re ecting the square about the mi axes; ?i corresponds
to re ecting the square about the diagonals, di.
D5 = f?0;?1;?2;?3;?4;?0;?1;?2;?3;?4;?5g where ?i corresponds to rotating the
pentagon clockwise 2?i5 radians and ?i corresponds to re ecting the pentagon about the
lines joining angles and the midpoints of their opposite sides.
D6 = f?0;?1;?2;?3;?4;?5;?1;?2;?3;?4;?5;?6g where ?i corresponds to rotating the
hexagon clockwise 2?i6 radians and ?i corresponds to re ecting the hexagon about the
lines connecting opposite vertices and the lines joining midpoints of opposite sides.
The preferred method for representing permutations in Sn is disjoint cycle notation.
With this notation, start with a left parentheses, ?(?, followed by some number in the
domain f1;2;:::;ng. The next number to the right is the image of the flrst under the
8
mapping. This process continues until the flrst number is reached. As soon as one gets
back to the starting number, this string of numbers is closed ofi with a right parentheses,
?)?. Repeat this entire process, beginning with ?(? and a number not yet listed. If a
number is flxed by the permutation (if it is equal to its image) then it is denoted as a
single number in parentheses.
We begin with an example of a plain necklace made of three beads with two color
options. As we are dealing with three beads, the set A, positions of the beads, is the
vertex set of a triangle; A = f1;2;3g. Let G be the dihedral group D3; therefore, jGj=6.
Let B be the set of possible colors; in this example jBj=2. Label the vertices clockwise,
beginning at the top of the triangle. We flrst write the cycles formed by permuting the
necklace into itself. In other words, we apply the elements of D3 to the set A and write
down, using the disjoint cycle notation detailed at the beginning of this chapter, the
results of each permutation. Doing so for this example yields the following:
?0 (1)(2)(3)
?1 (123)
?2 (132)
?1 (1)(23)
?2 (2)(13)
?3 (3)(12)
Next, we use these cycle decompositions to flnd the number of permutations in D3
that have exactly k cycles; simply, we count the number of permutations above that have
one set of parentheses, two sets of parentheses, three sets, etc. We denote each number
9
as ck(G). Thus, c1(G) = 2;c2(G) = 3 and c3(G) = 1. Now, apply P?olya?s Enumeration
Theorem, with A, G and B as deflned earlier and N, the number of orbits, being the
number of possible unique necklaces.
N = 1jGj
3X
k=1
ck(G)?2k = 16[c1(G)?21+c2(G)?22+c3(G)?23] = 16[2?21+3?22+1?23] = 4:
Thus there are four possible plain, unique necklaces to be made with three beads and
two color options.
Now, if we add one more color option, obviously the number of possible unique
necklaces increases. However, since we are still using three beads, the only value from the
preceding example that changes is jBj=3. Thus, using P?oyla?s Enumeration Theorem,
the formula becomes:
N = 16
3X
k=1
ck(G)?3k = 16[2?31 +3?32 +1?33] = 10:
Thus there are ten possible unique necklaces to made using three beads of three colors.
Continuing in this fashion, we see that using three beads and having 1,2,3,4,5,6,... color
options there are 1,4,10,20,35,56,... unique necklaces possible.
Using four beads increases not only the size and aesthetics of the necklace, but also
the calculation of the number of possibilities. Instead of working with the vertices and
symmetries of a triangle as before, we now work with the vertices and symmetries of a
square. Let A be the set of vertices of a square; A = f1;2;3;4g. Let G = D4 with jGj=8.
For illustration purposes, let jBj=4, or let there be four color options for this necklace.
10
As in the last example, use the disjoint cycle notation to list the afiect of each
permutation of D4:
?0 (1)(2)(3)(4)
?1 (1234)
?2 (13)(24)
?3 (1432)
?1 (12)(34)
?2 (14)(23)
?1 (13)(2)(4)
?2 (24)(1)(3)
Usingthesedecompositions, wegetthatc1(G) = 2;c2(G) = 3;c3(G) = 2 and c4(G) =
1. Applying all of this information to P?olya?s Enumeration Theorem, we see: N=
1
8
P4
k=1 ck(G)?4k=18[c1(G)?41 +c2(G)?42 +c3(G)?43 +c4(G)?44]=18[2?41 +3?42 +2?
43 +1?44]=55.
Thus, there are 55 possible unique necklaces to be made using four beads and
choosing from four colors. In fact, using four beads and 1,2,3,4,5,6,7,... colors of beads,
there are 1,6,21,55,120,231,406,... possible unique necklaces to design.
Now, some of us have expensive tastes, so let us calculate how many unique necklaces
using flve beads there are from which to choose. As in the previous two examples, we
let A be the set of vertices of a pentagon, making A = f1;2;3;4;5g. Label the vertices
clockwise from one to flve. This means G = D5 and thus jGj=10. For calculation
purposes, let jBj=3. The cycle decomposition is as follows:
11
?0 (1)(2)(3)(4)(5)
?1 (12345)
?2 (13524)
?3 (14253)
?4 (15432)
?1 (1)(25)(34)
?2 (2)(13)(45)
?3 (3)(24)(15)
?4 (4)(12)(35)
?5 (5)(14)(23)
Thus c1(G) = 4;c2(G) = 0;c3(G) = 5;c4(G) = 0 and c5(G) = 1. Applying P?olya?s
Enumeration Theorem for three colors, we get:
N= 110 P5k=1 ck(G)?3k= 110[c1(G)?31 + c2(G)?32 + c3(G)?33 + c4(G)?34 + c5(G)?
35]= 110[4?31 +0+5?33 +0+1?35]=39.
Thus there are 39 gorgeous, unique necklaces to be designed using flve beads and
three possible colors. In general, for flve beads and 1,2,3,4,5,6,7,8,... colors, there are
1,8,39,136,377,888,1855,3536,... unique necklaces to be made.
Finally, we will determine how many really glamorous, unique necklaces can be
made using six beads. Let A = f1;2;3;4;5;6g, the set of vertices of a hexagon. Label
the vertices clockwise one to six. Let G = D6 makingjGj = 12. Let us make this necklace
worthy of giving Momma by using nine colors in the design, thus making jBj=9. The
cycle decompositions are as follows:
12
?0 (1)(2)(3)(4)(5)(6)
?1 (123456)
?2 (135)(246)
?3 (14)(25)(36)
?4 (153)(264)
?5 (165432)
?1 (16)(25)(34)
?2 (1)(26)(35)(4)
?3 (12)(36)(45)
?4 (13)(2)(5)(46)
?5 (14)(23)(56)
?6 (6)(15)(24)(3)
Thus c1(G) = 2, c2(G) = 2, c3(G) = 4, c4(G) = 3, c5(G) = 0 and c6(G) = 1.
Applying P?olya?s Enumeration Theorem, the formula becomes:
N= 112
6X
k=1
ck(G)?5k= 112[c1(G)?51 +c2(G)?52 +c3(G)?53 +c4(G)?54 +c5(G)?55 +
c6(G)?56] = 112[2?51 +2?52 +4?53 +3?54 +0+1?56] = 1505.
Therefore, we have 1;13;92;430;1,505;4,291;10,528;23,052;46,185;... options for de-
signing an elegant and expensive necklace using six beads (or gems) of 1,2,3,4,5,6,7,8,9,...
colors.
13
Bibliography
[1] Davis, T., \Polya?s Counting Theory",http://www.geometer.org/mathcircles (Sep-
tember 12, 2001).
[2] Fraleigh, J. B., A First Course in Abstract Algebra ,6th ed., Reading, MA: Addison-
Wesley,(1999).
[3] Van Lint, J. H. and Wilson, R. M., A Course in Combinatorics , New York, NY:
Cambridge University Press, (1992).
14