1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete math:Placing beads on a necklace

  1. Feb 23, 2013 #1
    1. The problem statement, all variables and given/known data

    There are 8 beads: 4 black, 3 white, and 1 red.
    How many ways can these be arranged on necklace?

    2. Relevant equations

    Just combinations nCm = (n-m)!/(m!).

    3. The attempt at a solution

    8C4 = 70, 4C3 = 24, and 1C1 = 1, so the total number of combinations is 95?

    Or do I multiply them, resulting in 1680 possibilities?
    Multiplication seems like the logical way of solving it, because it is a union of the sets of possibilities, but I haven't done this is a long time so I'm unsure.
     
  2. jcsd
  3. Feb 23, 2013 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The point of the "necklace" is that you are placing them circularly, not linearly- there are no "end" beads. So choose any one bead you want, the red one, say, and arrange the others on that. If you have 7 beads, 4 black and 3 white, in how many ways can you arrange them?
     
  4. Feb 23, 2013 #3
    Okay, so if I fix the red bead, then there would be 7C3 = 7C4 = 7*6*5/3/2 = 35. Then 35*8 for each choice of the red bead is 280 total. Is this correct?

    For context, this is a smaller problem in a larger problem that I'm working on for Polya-Burnside Enumeration.
     
  5. Feb 24, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You're right to take the red bead as a point of reference, but there's no reason to multiply by the number of positions it can occupy at the end. Those arrangements are all the same, as far as the necklace as an entity is concerned. Indeed, you need to remove some arrangements that you have counted twice (reflections).
     
  6. Feb 25, 2013 #5
    Thanks Haruspex, I'm accounting for the reflections and rotations D8 with the Polya-Burnside lemma
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Discrete math:Placing beads on a necklace
  1. Discrete Math (Replies: 0)

  2. Discrete Maths (Replies: 9)

  3. Discrete Math (Replies: 1)

  4. Discrete Math Question (Replies: 6)

Loading...