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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.