Discrete math:Placing beads on a necklace

  • Thread starter Thread starter hsetennis
  • Start date Start date
  • Tags Tags
    Discrete
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
4 replies · 3K views
hsetennis
Messages
117
Reaction score
2

Homework Statement



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

Homework Equations



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

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.
 
Physics news on Phys.org
The point of the "necklace" is that you are placing them circularly, not linearly- there are no "end" beads. So choose anyone 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?
 
HallsofIvy said:
The point of the "necklace" is that you are placing them circularly, not linearly- there are no "end" beads. So choose anyone 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?

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.
 
hsetennis said:
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?
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).
 
Thanks Haruspex, I'm accounting for the reflections and rotations D8 with the Polya-Burnside lemma