1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting Unique Necklaces

  1. Feb 19, 2009 #1
    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 cant 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.
     
  2. jcsd
  3. Feb 20, 2009 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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?)
     
  4. Feb 20, 2009 #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 cant 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.
     
  5. Feb 20, 2009 #4

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  6. Feb 20, 2009 #5
    But how do you determine what Q is mathematically?
     
  7. Feb 21, 2009 #6

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  8. Dec 7, 2010 #7
    thank you

    _____________________

    http://www.choosing-bead-necklaces.com/children.html" [Broken]
    http://www.choosing-bead-necklaces.com" [Broken]
     
    Last edited by a moderator: May 5, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Counting Unique Necklaces
  1. Proving Uniqueness (Replies: 0)

  2. Counting Palindromes (Replies: 3)

Loading...