Discrete math:Placing beads on a necklace

  • Thread starter Thread starter hsetennis
  • Start date Start date
  • Tags Tags
    Discrete
Click For Summary

Homework Help Overview

The problem involves arranging 8 beads of different colors (4 black, 3 white, and 1 red) on a necklace, considering the circular nature of the arrangement. Participants are exploring how to account for the unique arrangements given the constraints of the problem.

Discussion Character

  • Exploratory, Assumption checking, Problem interpretation

Approaches and Questions Raised

  • Participants discuss various methods for calculating arrangements, including combinations and the impact of circular arrangements. There is uncertainty about whether to multiply combinations or consider them as distinct arrangements due to the circular nature of the necklace.

Discussion Status

Some participants have provided insights into fixing a bead to simplify the arrangement process, while others have raised questions about the implications of reflections and rotations on the total count. The discussion is ongoing, with different interpretations being explored.

Contextual Notes

Participants mention the Polya-Burnside Enumeration as a relevant concept for addressing the problem, indicating that the discussion is situated within a broader mathematical context.

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
 

Similar threads

Replies
2
Views
2K
Replies
6
Views
2K
  • · Replies 2 ·
Replies
2
Views
10K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
6
Views
4K
Replies
7
Views
2K
  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 1 ·
Replies
1
Views
3K
Replies
6
Views
3K