I would like to get a general expression for arranging n letters such that any similar letters in them never come together (except SPACE).

For example :

Lets take AABBCCC and three spaces(represented by '-'). So we have 10 spaces to arrange these. Now the number of ways we can arrange this so that never two A's or two B's or two C's come next to each other, but the SPACES can come together and two letters seperated by a space are not considered together (So we can have two A's together if there is a SPACE in between them).

So we can arrange as ABC---ACBC, CA-BCA--BC, A-ABC-CB-C, etc. But can't arrange as CA-BBC-A-C (B together), A-B--CABCC (C together), AAB---CCBC (A & C together), etc.

It could be solved for every solution seperately, but I require a general expression for this such that we feed the total number of terms (10 in e.g.), no of distinct entities with the number of repetitions(in e.g. we have 2 A's, 2 B's and 3 C's and 3 SPACES) and get the solution.

This is because I need to make a computer program as my project on this topic and I am unable to figure out a way for this.

Any help would be appreciated.


  • $\begingroup$ How many different symbols will your final program handle? And how many of the same symbol maximum? A solution for the spaces is to just add $n$ different symbols instead of $n$ spaces. $\endgroup$ – Ragnar Dec 30 '13 at 4:48
  • $\begingroup$ possible duplicate of Permutation for arranging objects in such a way that no similar objects come together $\endgroup$ – Henning Makholm Dec 30 '13 at 4:50
  • $\begingroup$ @Ragnar My program will be given a string of 100 characters and could be having any number of distinct letters repeated any number of times. But only the spaces are allowed to be together. Also could you please elaborate on the solution you are saying. It would be really helpful to me. Thanks. $\endgroup$ – Anshuman 'xLR' Verma Dec 30 '13 at 5:55
  • $\begingroup$ @Henning Ya that was posted by me earlier but I soon realized that the question was quite different so I posted this again. $\endgroup$ – Anshuman 'xLR' Verma Dec 30 '13 at 5:57
  • $\begingroup$ Clarification: do you want an algorithm that outputs a legal solution, or a formula for the number of legal solutions? $\endgroup$ – Zur Luria Dec 30 '13 at 6:04

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.