Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/