Discrete math:Placing beads on a necklace

  • Thread starter hsetennis
  • Start date
  • Tags
    Discrete
In summary: 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.
  • #1
hsetennis
117
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
  • #2
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?
 
  • #3
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.
 
  • #4
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).
 
  • #5
Thanks Haruspex, I'm accounting for the reflections and rotations D8 with the Polya-Burnside lemma
 

1. What is discrete math?

Discrete math is a branch of mathematics that deals with objects that can only take on distinct, separate values. It is used in fields such as computer science, engineering, and cryptography.

2. How is discrete math related to placing beads on a necklace?

Placing beads on a necklace involves arranging a finite number of objects in a specific order, which is a fundamental concept in discrete math. The act of placing beads on a necklace can be represented and analyzed using various discrete mathematical techniques, such as permutations and combinations.

3. What is the significance of placing beads on a necklace?

Placing beads on a necklace is a common problem in discrete math that has real-world applications in areas such as jewelry making and manufacturing. It also serves as a useful exercise for practicing combinatorics and counting principles.

4. How do you determine the number of ways to place beads on a necklace?

The number of ways to place beads on a necklace can be calculated using the formula for permutations with repetition, which is n^r, where n is the number of distinct beads and r is the number of positions on the necklace. For example, if you have 3 different types of beads and a necklace with 5 positions, there are 3^5 = 243 possible ways to place the beads on the necklace.

5. Can you explain the concept of rotational symmetry in relation to placing beads on a necklace?

Rotational symmetry refers to the property of an object to have a rotational symmetry of order n if it can be rotated by a certain angle and still appear the same. In the context of placing beads on a necklace, this means that some arrangements of beads may appear identical when rotated, reducing the total number of unique arrangements. This concept is important to consider when calculating the number of ways to place beads on a necklace.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
9K
  • Precalculus Mathematics Homework Help
Replies
3
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
Replies
14
Views
3K
Back
Top