Pages

Tuesday, September 25, 2012

Necklaces

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:

Sravan said...

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

Unknown said...

There is something wrong in your solution. Try again.