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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.