Possible Duplicate:
In how many ways we can put $r$ distinct objects into $n$ baskets?

Need some guidance with the following problem : There are 'n' different types of objects which needs to be placed in a circle of length 'r' , such that no two adjacent items are of the same type. Repetition is allowed.

eg. n = 4 {a,b,c,d} and r = 3 , the circular permutations are 
a b c
a b d
a c b
a c d
a d b
a d c
b c d
b d c

We do not include a permutation like 'b d a' , since that is the same as 'a b d'. Nor do we include a permutation like 'a a d' or 'a d a' since they do not satisfy the adjacency condition.

Similarly for n = 4 {a,b,c,d} and r = 4, 'a b a b' is valid, but 'a b b c' is not.

Is there a general solution or method that I can follow to solve this problem?


marked as duplicate by joriki, Rudy the Reindeer, Henry T. Horton, mdp, Chris Eagle Oct 4 '12 at 15:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Same question was asked and answered recently. It has been asked a few times in the last couple of days, Same problem, same source. $\endgroup$ – André Nicolas Oct 2 '12 at 9:20

Yes, it is.

There is a good article about combinations and variations in codeproject. You need for "Combinations (i.e., without Repetition)" there.

Also if you familar with C# you can use simple and short solution from stackoverflow.


Not the answer you're looking for? Browse other questions tagged or ask your own question.