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

### 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

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?

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/
```
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