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

### No Three Red Beads Together

```
Date: 09/16/2001 at 09:23:03
From: jenny
Subject: Permutation

Given 10 beads on a necklace, 6 white and 4 red, how many ways can the
```

```
Date: 09/16/2001 at 11:19:26
From: Doctor Anthony
Subject: Re: Permutation

We can first find the total number of arrangements with no
restriction, then subtract the number of arrangements with 3 or 4 red

For the total number of necklaces with no restriction we must use
Burnside's lemma. Here we are dealing with the dihedral group
symmetries of a 10-sided regular polygon in both rotation and
reflection. The lemma states that the number of distinct
configurations will be the number of group actions that keep colours
fixed divided by the order of the group (20 in this case, 10
rotational symmetries and 10 reflective symmetries).

The rotational symmetries that keep colours fixed will be the identity
(rotation through 360 degrees) and, because of the 4 red beads,
rotation through 180 degrees. For reflective symmetries we can reflect
either 2 white or 2 red beads on the axis of reflection. There will be
5 axes of reflection of each type.  Putting these results into table
form we have

Action               Number that keep Colours Fixed
----------           ---------------------------------
Rotation 360 deg.        10!/[6!4!]  =  210
Rotation 180 deg.         5!/[3!2!]  =   10
Reflect(1) White        5 x 4!/[3!]  =   20
Reflect(1) Red          5 x 4!/[2!2!]=   30
Reflect(2)              5 x 5!/[3!2!]=   50
---------
Total =  320

Then using Burnside's lemma the number of distinguishable
configurations is this number divided by the order of the group (=20).

320
Number of distinct necklaces = ----- = 16
20

From this we must subtract the number with 3 or 4 red beads next to
each other. A diagram will quickly establish what this number is. If
you group 3 of the red beads into a single block there will be 7 other
beads, one of which is also red. For exactly 3 red beads together this
extra bead could be in one of 6 gaps between the white beads. However,
we must divide this number by 2, since we could view the necklace from
either side. So there are 3 configurations with exactly 3 red beads
together. With 4 red beads together, there is only 1 configuration.

The number of configurations with 3 or 4 red beads together = 3+1 = 4

Number of configurations such that no 3 red beads are together

= 16-4

= 12

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Discrete Math
High School Discrete Mathematics
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