Printable View
I really need some help. I need to find the possible necklaces that can be made from 7 identical beads of one color and 5 identical beads of a different color. I think it has something to do with the symmetrical group of a dodecagon . I'm also thinking that the rotations shouldn't be counted because they would create a necklace that is indistinguishable from the previous one. Is this true?
here is what i think (i'm really bad at combinatorics, so this might not be right):
suppose we label the positions where we put our beads as 1-12. we select 5 beads from a box of beads of number 2 to put in the 12 possible positions. what we are essentially doing is choosing 5 of the 12 positions to be "color number 2 beads". thus there are "12 choose 5" ways to do this:
12!/[(5!)(7!)] = (8*9*10*11*12)/(5!) = (8*9*10*11*12)/(2*3*4*5) = 6*11*12 = 792 possible necklaces, not counting duplicates.
let's call this set of 726 necklaces X. we're going to act on this set with a cyclic group of order 12 (the rotation group of the dodecagon). thus the number of non-duplicate necklaces is the number of orbits of X. we will call an necklace fixed by g in our rotation group, if g maps a color one bead to a color one bead, and a color two bead to a color two bead.
to do this properly, we need to invoke Burnside's Lemma:
where X/G is the partition of X into its orbits, and Xg is the number of elements of X fixed by g.
let's call a rotation by 1/12 of a circle (shifting one bead over) r. so G = {e,r,r2,...,r11}.
first, the easy one: how many of our 792 configurations are fixed by e? all of them.
how many are fixed by r? well, if they are fixed by r, we must have only beads of ONE color, but we have TWO, so: none of them. similar reasoning applies to r-1 = r11.
how about r2? if a coloring is fixed by r2, it must have period 2 (it repeats every two beads), so we only need to consider the possible colorings of the first 2 beads. suppose we use B (for black) for color number 1, and W (for white) for color number 2. here are our possible colorings:
BB <---leads to 12 black beads
BW <---leads to 6 black, and 6 white beads
WB <---see above
WW <---leads to 12 white beads
so no coloring can be fixed by r2, or similarly, by r10.
ok, on to r3 (of order 4). possible colorings of the first 3 beads:
BBB <---no, all black
BBW <---no, 8 black 4 white
BWB <---no, 8 and 4 again
BWW <---no, 4 black and 8 white
(verify that none of the 4 remaining colorings of the first 3 beads will work). this means no coloring can be fixed by r3 or r9.
how about r4? again, we only need to consider the first four beads:
if we have 0 W beads in the first 4, and r4 fixes the coloring, all the beads are black.
if we have 1 W bead in the first 4, we wind up with 3 W and 9 B.
if we have 2 W beads in the first 4, we wind up with 6 W and 6 B.
if we have 3 W beads in the first 4, we wind up with 9 W and 3 B.
if we have 4 W beads in the first 4, all the beads are W.
so none of the colorings can be fixed by r4, or r8.
let's skip ahead and look at r6 next. since we have an odd number of each color, and since any pattern of period 6 will contain an even number of each color, no coloring is fixed by r6.
that leaves just r5, and r7.
5 B beads is obviously not going to work (the first 10 beads would have to be B).
4 B beads is "too many" we'd wind up with at least 8 B beads total, and we only have 7.
5 W beads wouldn't work, either, it winds up giving us 10 W beads in the first 10, and we only have 5.
4 W beads is too many, we'd have at least 8 W beads, and we only have 5.
3 W beads is also too many, we get 6 W beads in the first 10.
so the only viable combination is 3 B beads, 2 W. suppose the first bead is W. then we have 4 W beads in the first 10, and the last W bead we can use in the 11th place. so if the first bead is W, the second bead CAN'T be.
this means we might have:
WBWBB
WBBBW
WBBWB
furthermore, for the pattern to "match up" after it wraps around, the 3rd bead must be W, and the 4th bead B. so of the 3 we've narrowed it down to, only WBWBB is still a possibility. let's see what happens:
WBWBB WBWBB WB rotate by 5:
WBWBB WBWBW BB <---not a match.
so the first bead cannot be W. so now assume that the first bead is B. if the 2nd bead is also B, we get B beads in place 11 & 12, leading to 8 B beads in all. so the second bead has to be W. so we have:
BWBBW
BWBWB
BWWBB. just as with having the W bead first, the 3rd bead has to be B. this gives us 2 to choose from:
BWBBW BWBBW BW rotate by 5:
BWBBW BWBWB BW <--not a match.
BWBWB BWBWB BW rotate by 5:
BWBWB BWBWB WB <--not a match.
i leave it to you to show that r7 also does not fix any colorings.
so by burnside's lemma, we have:
|X/G| = (1/12)(792) = 66 distinct necklaces.
Wouldn't we need to divide this by 2 to take away the reflections made by flipping the necklace over? Also, because it's circular, should the 12! be (12-1)! I really don't know...I'm guessing. I'm supposed to use Burnside's theorem to do this problem.
I though about this problem a lot and came up wit the way to solve it, so I though I would share. Your help got me started, but wasn't completely right.
Because there are 12 bead, we think of the do-decagon and it group of symmetries. There are 24 in the symmetric group so that's a place to start. There are 12 rotations, the identity being one and 12 flips or reflections. There are six that flips from vertex to vertex and six that flip from mid-point to mid-point. So now I need the number fixed be each symmetry. Because there are 7 of one color and 5 of another the only rotation that fixes colors is the identity. (This would not be true if both number of beads were even.) That total is 12!/7!5!= 792. Of the flips, the mid point to midpoint flips fix nothing. (I had to draw this out to convince myself, but it's true.) The vertex to vertex flip, remember there are six, do fix things, but only when the colors are at opposite poles. There are 6 ways to do this. So on each of those place one red and one white at each vertices and then figure out the ways to place the other beads. I cut it in half and though of the five place on each side of the vertices and came up with (5!/3!2!)=60 then multiplied that by 2 for the other side to get 120. So the number of orbits equals (792+0+120+0)/24=38. So, there are 38 distinct necklaces that can be made from 7 beads of one color and 5 of another.
P.S. My professor said I did this exactly right.
Yeah!
you are correct....i forgot about the flips (which might preserve configurations that can't be rotated into one another).Quote:
Originally Posted by amyw
if our axis of reflection runs bead to bead, then one bead must be B and the other W (so that we have an even number of each color to match up by reflecting). then any combination of bead colors on one side can be matched up on the other side, so long as we have 3B and 2W. there are 5 choose 2 (= 5 choose 3) ways to create these colorings: 5!/(3!2!) = 120/12 = 10 coloring that have a B bead at position 1, a W one at position 7, plus 10 more than have a W bead at position 1 and a B bead at position 7.
that makes 20 colorings fixed by each reflection that fixes a pair of opposite beads, and we have 6 such pairs, for an addition 120. the reflection about an axis between two beads cannot fix anything, because we would need an even number of each color (the two havles must match). so we do get:
(1/24)(792 + 0 + 0 + 0 + 0 + 0 + 20 + 20 + 20 + 20 + 20 + 20 + 0 + 0 + 0 + 0 + 0 + 0) = (1/24)(912) = 38.
( i convinced myself of this by considering the analogous situation with 8 beads with 5 of one color and 3 of another, where the configurations are much smaller and easier to count).
good job!