We say that two necklaces are different if one cant be obtained from another by rotating it (by whatever angle). Calculate the total number of different necklaces possible with N beads of R(<N) different colors.

Courtesy : Prof. Sharad Sane - IIT Bombay

## 2 comments:

Consider the non circular case first.

The total number of ways of permuting n beads with r different colors is the coefficient of x^n in the expression

n! * (1+x/1!+x^2/2!+x^3/3!+...)^r = c, say

Now in all such permutations, each one when cyclically rotated will give the same permutation in the circular case. This can be done in n ways.

So the number of necklaces should be c/n

There is something wrong in your solution. Try again.

Post a Comment