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