Results 1 to 5 of 5

Math Help - symmetrical groups questions

  1. #1
    Junior Member
    Joined
    Oct 2012
    From
    Austin, Texas
    Posts
    36

    symmetrical groups questions

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,366
    Thanks
    735

    Re: symmetrical groups questions

    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:

    |X/G| = \sum_{g \in G} |X^g|

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2012
    From
    Austin, Texas
    Posts
    36

    Re: symmetrical groups questions

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2012
    From
    Austin, Texas
    Posts
    36

    Re: symmetrical groups questions

    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,366
    Thanks
    735

    Re: symmetrical groups questions

    Quote Originally Posted by amyw View Post
    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).

    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Groups of symmetries questions.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 6th 2012, 07:08 AM
  2. Symmetrical about the mean question
    Posted in the Statistics Forum
    Replies: 2
    Last Post: December 8th 2010, 02:22 PM
  3. express in a symmetrical form??
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: November 24th 2009, 09:45 PM
  4. Symmetrical Functions
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 7th 2009, 04:49 PM
  5. Point symmetrical
    Posted in the Calculus Forum
    Replies: 2
    Last Post: June 25th 2008, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum