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

[SammC]

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.

 

[CompuChip]

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?)

 

[SammC]

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.

 

[CompuChip]

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?

 

[SammC]

But how do you determine what Q is mathematically?

 

[CompuChip]

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?

 

[DrewBlay]

thank you

_____________________

http://www.choosing-bead-necklaces.com/children.html"
http://www.choosing-bead-necklaces.com"