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

  • Thread starter Thread starter SammC
  • Start date Start date
  • Tags Tags
    Counting
Click For Summary

Discussion Overview

The discussion revolves around the combinatorial problem of determining the number of distinct necklaces that can be formed using n beads of k colors, considering the effects of flipping and rotating the necklaces. The scope includes theoretical exploration and mathematical reasoning related to counting distinct arrangements.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant states that for n=3, there is only 1 distinct arrangement of beads when considering flipping and rotation.
  • Another participant challenges this by suggesting that there are actually 3 distinct arrangements when considering all permutations and their reversals.
  • It is proposed that if n beads are distinguishable, the total arrangements without considering equivalence is n!.
  • A participant suggests that the number of distinct necklaces can be calculated as n!/Q, where Q represents the number of equivalent arrangements due to rotations and flips.
  • There is a question about how to mathematically determine the value of Q for a given arrangement of beads.
  • Discussion includes the need to consider rotations of the arrangement to identify equivalent necklaces.

Areas of Agreement / Disagreement

Participants express differing views on the number of distinct arrangements for n=3, indicating a lack of consensus on the initial claims. The discussion on how to calculate Q and the implications of rotations and flips remains unresolved.

Contextual Notes

Participants have not yet reached a clear mathematical formulation for Q, and assumptions about the nature of the beads (distinguishable vs. indistinguishable) may affect the conclusions drawn.

SammC
Messages
17
Reaction score
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
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 :-p?)

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?)
 
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.
 
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?
 
But how do you determine what Q is mathematically?
 
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?
 
thank you

_____________________

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

Similar threads

MHB How many necklaces can we create?
  • · Replies 44 ·
2
Replies
44
Views
6K
How Many Unique 5 White and 5 Black Bead Necklaces Can Be Made?
  • · Replies 2 ·
Replies
2
Views
2K
Discrete math:Placing beads on a necklace
  • · Replies 4 ·
Replies
4
Views
2K
How many ways can you color the edges of a hexagon in two colors?
  • · Replies 1 ·
Replies
1
Views
7K
Undergrad What is the value of n in Reverse Combinatorics problem?
  • · Replies 3 ·
Replies
3
Views
2K
Comp Sci Finding Cousins of Giuga Numbers: Can You Solve This Prime Number Puzzle?
  • · Replies 32 ·
2
Replies
32
Views
5K
PLL - How to find all the gains of a PI corrector and fix Ki ? MATLAB
  • · Replies 2 ·
Replies
2
Views
2K
How many words of length n are there in this regular language?
  • · Replies 1 ·
Replies
1
Views
2K
Challenge Math Challenge - September 2021
  • · Replies 100 ·
4
Replies
100
Views
12K
What is the best Big-O function for the equation |n + 2| − |n / 3|?
  • · Replies 2 ·
Replies
2
Views
3K