How many distinct necklaces can be made with n beads and k colors?

  • Thread starter SammC
  • Start date
  • Tags
    Counting
In summary, the problem is to determine the number of distinct necklaces that can be made using n beads with different colors, where flipping the necklace does not count as a distinct one. The attempt at a solution involved finding a formula for N beads with K different colors, which simplified down to (n-1)! / 2 for N=K. However, there was uncertainty about the correctness of this formula and a request for a different approach. It was suggested to use a counting argument and consider the number of equivalent necklaces in a specific sequence. The number of rotations that give a new sequence was also discussed.
  • #1
SammC
17
0
The problem statement
Suppose you have n beads, each with a different color. You need to string these beads into a necklace. How many distinct necklaces can you make? (A necklace flipped over remains the same and does not count as a distinct necklace.)


The attempt at a solution
I decided to figure out the first couple necklaces:

n=3: 3 beads can only be arranged 1 distinct way that can't be duplicated by flipping or rotating.

n=4: 4 beads can be arranged 3 ways.

Browsing the internet, i found some fairly complicated equations that I didn't really understand, but I found one for N beads with K different colors, which simplified down to (n-1)! / 2 for N=K. I tried this out for n=3 and 4, and it worked for both of those, but that's far from proof that it works beyond that.

What i really want to know is if this formula is correct, and if not, a way of thinking about this problem that will lead me down the path to a correct formula.
 
Physics news on Phys.org
  • #2
Let's start by leaving out the requirement of "invariance under flipping".
Suppose you have N beads of different colors, so they are all distinguishable. How many different necklaces can you make out of them?
If you haven't seen such a question before, try a counting argument... how many possibilities are there for the first? How many for the second? How many for the third? Continue like this... then what do you do with all those numbers (multiply them together? add them? exponentiate them :tongue:?)

Also, I think I am missing a small point... how is there only one for n = 3?
Suppose you have Red, Green and Blue beads, then you can make the six combinations
RGB, BGR
RBG, GBR,
GRB, BRG
where the ones listed on one line are the same (by reversal). So that gives you three possibilities, not one, doesn't it?
Or are you allowed to do cyclic permutations (e.g. RGB is the same as GBR and BRG?)
 
  • #3
If you purely want to choose all the possible combinations, it would be n!.

The reason n=3 results in 1 is because you assume that the first and last element are connected (like in a necklace) and things that can be made from rotating that necklace or flipping it can't be counted again. So for the triangle that would be formed using RGB, you there is no other combination that cannot be formed by rotating or flipping that triangle.
 
  • #4
Ah, I see.
So in principle we have n! combinations. Now let's consider one specific necklace and count the number of equivalent ones. If there are Q equivalent necklaces then the number you are looking for will be n!/Q, agreed?

If you have a necklace, ABCD...LMN, how many are there which are actually the same?
 
  • #5
But how do you determine what Q is mathematically?
 
  • #6
So first let's look at the rotations.
How many possible rotations of N are there that give a new sequence?
So if we have ABCD...LMN, then we want to consider BCD...LMNA and CDE...LMNAB as equivalent. Do you see how many possibilities this gives?
 
  • #7
thank you

_____________________

http://www.choosing-bead-necklaces.com/children.html"
http://www.choosing-bead-necklaces.com"
 
Last edited by a moderator:

1. How do you determine the number of unique necklaces?

The number of unique necklaces can be determined by using the formula (n!/2n), where n is the number of beads and 2n represents the total number of possible rotations and reflections.

2. Can two necklaces be considered unique even if they have the same beads?

Yes, two necklaces can still be considered unique even if they have the same beads, as long as the order or arrangement of the beads is different.

3. Are there any limitations to counting unique necklaces?

Yes, there are limitations to counting unique necklaces. The formula mentioned earlier only applies to necklaces with an even number of beads. For necklaces with an odd number of beads, a different formula (n!/n) must be used.

4. How does the symmetry of the beads affect the number of unique necklaces?

The symmetry of the beads plays a role in the number of unique necklaces. If the beads have rotational symmetry, then the number of unique necklaces will be fewer compared to beads with no symmetry. This is because some necklaces will be identical when rotated.

5. Are there any real-life applications of counting unique necklaces?

Yes, counting unique necklaces has applications in various fields such as chemistry, genetics, and computer science. In chemistry, it can be used to determine the different isomers of a molecule. In genetics, it can be used to understand the different possible combinations of genes in an organism. In computer science, it can be applied in coding and cryptography.

Similar threads

  • Linear and Abstract Algebra
2
Replies
44
Views
5K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
32
Views
3K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
6K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
538
  • Introductory Physics Homework Help
Replies
30
Views
490
Back
Top