Alex is a necklace maker. He likes this task because it's challenging, fascinating and of course makes a lot of money. Now, he wants to make a necklace consisting of n beads. The beads are connected in the following fashion:

1) Bead i (1 < i < n) is connected with bead i - 1 and bead i + 1.

2) The first bead is connected with the second bead and the nth bead.

3) The nth bead is connected with the first bead and the (n-1)th bead.

Now he has K colors and each bead can be colored using one of the K colors.He has to find the number of possible necklaces he can make using these colors. Two necklaces will be considered same if one can be rotated to another.

For example, say there are 4 beads in the necklace and he has two colors yellow and green, then there are 6 possible necklaces. They are:

enter image description here

  • 2
    $\begingroup$ Just to be clear, are you considering necklaces which are reflections of each other to be different? So B-B-R-B-R-R- and B-R-B-B-R-R- are different necklaces? $\endgroup$ – Mike Earnest Oct 8 '14 at 8:39
  • $\begingroup$ Simpler version of the same question as @MikeEarnest: Are A-B-C and C-B-A considered distinct cases? $\endgroup$ – Marc van Leeuwen Oct 8 '14 at 9:26
  • $\begingroup$ Relevant: OEIS A000029 or OEIS A000031 $\endgroup$ – MJD Oct 8 '14 at 16:22
  • $\begingroup$ There is a list of Burnside computations at MSE Meta. This includes several examples of necklaces under various constraints by different users. $\endgroup$ – Marko Riedel Oct 8 '14 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.