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 
beads be arranged so that no three red beads are together?

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 
beads next to each other.

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 
about axes through opposite beads or about axes through midpoints of 
opposite sides. When reflecting about axes through beads we must have 
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/