Permutations in a Necklace

Date: 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/