Permutations in a NecklaceDate: 07/04/99 at 07:14:36 From: Mark Romer Subject: Permutations and Combinations Hi - I am wondering if you could explain how to get the formulae of the number of permutations in a necklace with the combination of AABB. I already understand how to get the formula or rule for AABC - by simply fixing the two A's, allowing only the B and C to rotate into new permutations. The formula that I used for this was (4-2)!/2 equal to 1 permutation. As you see, you take two off, because they are fixed, and divide by two to get rid of the mirror images when flipped. But for AABB how can I fix the A or B to get the formula to find the number of permutations? Can you please help me? I am stuck! Yours kindly, Mark Romer Date: 07/08/99 at 11:00:23 From: Doctor Anthony Subject: Re: Permutations and Combinations When you have a necklace of coloured beads with all the colours occurring more than once you are into a problem of MUCH greater complexity than when a particular colour occurs only once and you can use that colour as a fixed marker. You can read the background theory in books on combinatorics under the heading of cyclic Groups, groups of permutations, Burnside's lemma, Polya enumeration methods and so on. I will work through the problem with you showing what to do, but if you want full justification of the method you should consult a textbook on combinatorics. Burnside's lemma states that the number of distinguishable necklaces is the sum of the group actions that keep the colours fixed divided by the order of the group. To make this idea clearer I will assume that we have a necklace with 2 red, 2 blue and 2 green beads, and we must find the number of distinguishable necklaces that could be made, assuming that we can view the necklace from either side. We can think of the 6 beads as the 6 vertices of a regular hexagon and the string connecting the beads as the sides of the hexagon. Now if you are familiar with the symmetries of a hexagon there are 6 rotational symmetries, that is you can rotate a hexagon through multiples of 60 degreees without any apparent change in its appearance. There are also 6 reflection symmetries, 3 about a line through pairs of opposite corners and 3 about a line through the midpoints of pairs of opposite sides. These 12 symmetries form the Dihedral group D6 of order 12, and we must now count the group actions on our hexagon (having 2 R, 2 B and 2 G corners) which keep the colours fixed. Rotations: If you think about a red bead, it is clear that with only one other red bead you could not rotate the hexagon through 60 degrees or 120 degrees and have the other red bead in a position to which you move AND the other red bead move to your original position. With 180-degree rotation you could satisfy both these conditions. So the possible rotations that keep colours fixed are through 180 degrees or 360 degrees (which is the same as the identity of 0 degrees). The group actions that keep colours fixed are therefore Identity, for which you could have 6!/(2!2!2!) different arrangements, and rotation through 180 degrees which could give 3!/(1!1!1!) different arrangements. (Note that if you fix the order of the three colours on one side of a line of symmetry you automatically fix the positions on the other side). So the sum of the group actions that keep colours fixed during rotations is 6!/(2!2!2!) + 3!/(1!1!1!) = 90 + 6 = 96 Reflections: First consider reflections about a line of symmetry passing through the midpoints of opposite sides. There are 3 such axes of symmetry and for each, the order of the three beads on one side could be permuted in 3! = 6 ways. So for this type of reflection there are 3 x 6 = 18 group actions that keep colours fixed. Next consider reflections about a line of symmetry through opposite corners. Again there are 3 such lines of symmetry. Clearly the corners on the line of refection must have the same colour and this colour could be chosen in 3 ways. The two other beads on one side of a line of symmetry could be arranged in 2 ways, so altogether there are 3 x 3 x 2 = 18 group actions that keep colours fixed. Summarizing all these we have: Rotations: Sum of group actions = 96 Reflections(1) " = 18 Reflections(2) " = 18 ------------- Total = 132 Finally we apply Burnside's lemma, that the number of inequivalent configurations is this sum divided by the order of the group (12 in this case). Number of different necklaces = 132/12 = 11 We turn now to the number of necklaces with 4 beads, 2 red and 2 blue. This time we think of the beads as being at the 4 corners of a square, and we must consider the symmetries of a square. There are rotations through multiples of 90 degrees (4 of these) and reflections about the axis of symmetry through opposite corners (2 of these axes) and about midpoints of opposite sides (2 of these also). We are dealing with the dihedral group D4 of order 8. Rotations: Only 180 degrees and 360 degrees. The identity rotation (0 or 360 degrees) gives 4!/(2!2!) different arrangements and rotation through 180 degrees gives 2!/(1!1!) different arrangements. The sum of the group actions that keep colours fixed during rotations is: 4!/(2!2!) + 2!/(1!1!) = 6 + 2 = 8 Reflections: About an axis through midpoints of opposite sides. There are 2 such axes and the beads on one side can be arranged in 2 ways. This gives a total of 2 x 2 = 4 arrangements. About an axis through opposite corners. There are 2 such axes and the colour of the corners on the axis of reflection can be chosen in 2 ways. This gives a total of 2 x 2 = 4 arrangements. Summarizing all these we have: Rotations: Sum of group actions = 8 Reflections(1) " = 4 Reflections(2) " = 4 ------------- Total = 16 Finally we apply Burnside's lemma, that the number of inequivalent configurations is this sum divided by the order of the group (8 in this case). Number of different necklaces = 16/8 = 2 This seems a lot of hard work for a rather trivial result, but the method is perfectly general. Try your luck with a necklace of 12 beads having 6 beads that are red, 2 blue, 2 green and 2 yellow. (You should get an answer of 3530 different necklaces). - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 07/13/99 at 03:29:08 From: Mark Romer Subject: Permutations and combinations Dear Dr. Math, I GREATLY thank you for pointing me in the right direction for finding the number of permutations for a necklace with the combination of AABB. Now I understand the long process of using Burnside's lemma with combinatorics. But I am wondering if you could also help me with a similar problem using the same kind of method. How can I arrive at a formula for, for example, let's say a necklace with a combination of AABC, not AABB? I don't think the same method will work, as you have kindly shown with AABB, because in rotations, although we can have it work for 360 degrees (4!/(2!1!1!), when dividing it by two for 180 degrees it is not mathematically correct, as shown below: (2!/(1!0.5!0.5)) As you see, the two 1's can not be divided by two and then permuted. And let's say we also have a necklace with 6 beads with the combination AABCDE. How can I find the number of permutations? Also in reply to your answer, does it work for prime numbers of beads like 5 (3 red and 2 blue)? Yours kindly, Mark Romer Date: 07/13/99 at 08:43:45 From: Doctor Anthony Subject: Re: Permutations and combinations We think of the symmetries of the square which is the dihedral group of order 8. Four rotational symmetries and four reflection symmetries, 2 about lines through midpoints of opposite sides (reflection(1)) and 2 about lines through opposite corners (reflection(2)). With this set of letters there are no rotational symmetries EXCEPT the identity, for which we get 4!/(2!) = 12 arrangements. Reflection(1) - No symmetries that keep colours fixed. Reflection(2) - About line through B and C as opposite corners. = 2 on swapping B and C and 2 axes as the line of reflection = Total of 2 x 2 = 4 arrangements Total group actions that keep colours fixed = 12 + 4 = 16 and applying Burnside, the number of inequivalent necklaces = 16/8 = 2. You need to draw out a figure and check what happens when you reflect the square in a line of symmetry and see whether or not the colours remain fixed during this operation. If ALL the colours are not fixed then it must not be added to the total of symmetries used in our calculation. For a necklace with 5 coloured beads, say 3 red and 2 blue, you must think of the symmetries of a pentagon and go through exactly the same sort of calculation as I did with the square. I will leave you to try it, but write in again if you have problems with it. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 07/15/99 at 03:23:36 From: Mark Romer Subject: Permutations and combinations Dear Dr. Math, I tried to work through your method of finding the number of permutations in a necklace with the combination of AABC. Although I understood the process, I still feel that I have not completely understood how to arrive at the rotations. I tried to use the similar process you told before to find the number of permutations in a necklace of 5 beads in the combinations of AABBB (2 red beads and 3 blue beads). But I am still having trouble finding the exact number of rotational and reflection symmetries, with this combination using a pentagon. I already realise that there are 3 reflection line points, and I think the rotational symmetry is five. Maybe this is because there is a prime number of vertices. The reason is that I can't distinguish the two reflections, either going through corners or through the midpoints. Can you please also go through this example with me by finding the number of permutations? I feel this is the only way that can fully understand the process involved. Greatly appreciated, Mark Romer Date: 07/15/99 at 06:04:25 From: Doctor Anthony Subject: Re: Permutations and combinations It is a good idea to draw out a regular pentagon and think of the ways that you could arrange the 2 reds and 3 blues at the vertices, and in how many ways you could rotate and reflect the figure such that you end up with exactly the same coloured corners as you started with. Think first of rotations. The angles through which a pentagon can be rotated so that it appears not to have moved are multiples of 72 degrees. One full rotation is 5 x 72 = 360 degrees. With the colours given (2 red, 3 blue) there is no way you can rotate through 72, 144, 216, 288 degrees such that both red corners remain red after the rotation, so the only rotation that keeps colours fixed is 360 degrees, and the number of possible colourings that remain fixed under 360 degree rotation is the number of permutations of 2 red and 3 blue beads = 5!/(2!3!) = 10. We next consider reflections. For a pentagon the only type of reflection is along an axis from a vertex to the midpoint of an opposite side. We could not have a red on this line of symmetry because the other red would move and change the colour of a corner, so we must have one blue on the line of reflection. Then we have a red and blue on each side of the line of symmetry. We must now count how many arrangements are possible. We have 5 axes of symmetry that can be lines of reflection. We have 2 positions for the red and blue on one side of the line of reflection. Total arrangements that remain fixed under reflection = 5 x 2 = 10. Total of all group actions (rotation and reflection) that keep colours fixed = 10 + 10 = 20. Burnside's lemma then states that the number of different necklaces will be this total divided by the order of the group. The order of the group is 10, so we get Number of different necklaces = 20/10 = 2. (This seems a lot of hard work for a trivial result. However, the method is what is important.) You might like to draw out the two possible configurations (in one the two reds are next to each other; in the other they have a blue between them) and satisfy yourself that no more than 2 different necklaces are possible. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/