Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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 
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/   
    
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/