Associated Topics || Dr. Math Home || Search Dr. Math

### Permutations of Beads on a Necklace

```
Date: 09/07/99 at 09:16:05
From: Mark Romer
Subject: Permutations and combinations

Dear Dr. Math,

Last time I contacted you, you kindly told me how I could find the
number of permutations for a necklace that has a color occurring more
than once e.g. AABB, AAABBBCCC, or AAABB. You did this by going
through Burnside's Lemma and finding the total number of reflections
and rotations that kept colors fixed and dividing it by the order of
the group.

http://mathforum.org/dr.math/problems/romer07.04.99.html

But I am having trouble working through the combination AAABBB. I can
find the total number of reflections, but I can't determine the
rotations part. I know that there are rotations through 120 degrees
and 360 degrees, but I seem to be two rotations short.

We are dealing with a hexagon, with a group order of 12. There are 6
rotational symmetries and 6 reflection symmetries altogether, through
opposite vertices and through midpoints of opposite sides.

ROTATIONS

6!/(3!*3!) + 2!/(1!*1!) = 22

REFLECTIONS

There are no reflections through midpoints of opposite sides, but
reflection symmetry through opposite corners. As you see on the
diagram the A and B beads are on the axes of symmetry that can be
swapped 2 times, with different beads on one side that can be
arranged 2! ways. We have 3 reflection symmetries through opposite
corners in hexagons, so the reflections that keep colors fixed are:

2 x 3 x 2! = 12

Summarizing rotation and reflection data:

Rotations:    Sum of group actions = 22 (?)
Reflections1: Sum of group actions =  0
Reflections2: Sum of group actions = 12
-----------------------------------------
TOTAL                              = 32

We apply Burnside's lemma, with our order of the group being 12,
because the sum of a hexagon's symmetries is equal to 12. The number
of different necklaces = 32/12 = ?

As you see, I am 2 rotations short of getting 36/12 = 3 different
arrangements. Can I multiply the 2 resulting from 2!/(1!*1!) by 2, so
I get 4, because through 120 degrees three sections are produced in
the hexagon, and I need to multiply it by 2 to count the other 2
sections? I think this way is right, but I am still unsure.

Can you show me how you figured out the rotations for the combination
AAABBB and show me the correct way?

Yours kindly,
Mark Romer
```

```
Date: 09/07/99 at 10:57:01
From: Doctor Anthony
Subject: Re: Permutations and combinations

Necklace with Beads AAABBB
---------------------------
We think of the symmetries of a hexagon, the dihedral group D6 of
order 12, and must count the group actions that keep colors fixed.

Rotations
---------
The usual symmetries of a hexagon allow 60 degree rotations but with 3
beads of one color and 3 of a second color we could have these at
120-degree separation, allowing rotations of +120, -120 and of course
360.

So the numbers of actions are:

360 degrees:  6!/(3! 3!)  = 20
120 degrees:              =  2  (swapping the colors)
-120 degrees:              =  2           "
----------
Total = 24

Reflections
-----------
We cannot reflect about midpoints of opposite sides and keep colors
fixed, but we can reflect about opposite corners, provided these
corners have beads of different colors.

For any reflection we can reverse the color of beads at the corners on
a line of reflection and also reverse the other beads on one side of a
line of reflection. This gives 2 x 2 = 4 arrangements. Also there are
3 axes of reflection, so total symmetries are 3 x 4 = 12.

Total of all symmetries that keep colors fixed = 24 + 12 = 36

Applying Burnside, the number of distinct necklaces = 36/(order of D6)
= 36/12
= 3

So with a necklace of 3 beads of one color and 3 beads of a second
color, the number of distinct necklaces is 3.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search