Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I encountered this question in a coding competition. The question:

Given a string, calculate the number of permutations of that string such that no two identical letters lie adjacent to each other.

Example:
Input: caat
Ouput: Possible permutations are acat, cata, atac, taca, atca , acta. Therefore the answer is $6$.

One way of calculating the answer is to calculate the answer for separate cases like when just $2$ identical letters are together, 3 identical letters are together and so on, and then to subtract this answer from $n!$, where $n$ is length of the input string.

P.S. I am looking for a closed form answer to this question.

Thanks in advance.

share|improve this question
    
You haven't asked any mathematical question. You've quoted a question from a coding competition, in which "calculate" presumably meant "compute". Are you looking for a simple closed formula that expresses the number of permutations in terms of the counts of the numbers of identical letters in the string? If you're looking for a good practical way to compute that number, I think the question would be better placed at stackoverflow.com. –  joriki Jan 16 '12 at 8:53
1  
Why not acta and atca are considered? –  Tapu Jan 16 '12 at 9:15
    
@Tapu you are correct. I have made the correction. –  gibraltar Jan 16 '12 at 9:56
    
@joriki I have clarified that i am looking for a closed form answer to this question. –  gibraltar Jan 16 '12 at 9:59

1 Answer 1

up vote 1 down vote accepted

I don't have a closed form and I doubt you'll find a nice one, but here's a recurrence relation that would allow you to compute the number of admissible strings by recursion.

Let the numbers of identical letters in the string be $n_1,\dotsc,n_k$. Consider what happens if you remove one instance of the $k$-th letter from an admissible string. The remaining string has $n_1,\dotsc,n_k-1$ letters, and it is either an admissible string or an inadmissible string with two identical letters adjacent. In the latter case, we can contract the two adjacent letters into one to get an admissible string. Thus, we can count the number of admissible strings like this:

$$n_ka(n_1,\dotsc,n_k)=\left(\sum_{i=1}^kn_i\right)a(n_1,\dotsc,n_k-1)+\sum_{i=1}^{k-1}(n_i-1)a(n_1,\dotsc,n_i-1,\dotsc,n_k-1)\;,$$

where the factor $n_k$ accounts for the fact that we can remove any of the $n_k$ instances of the $k$-th letter, the factor $\sum_i n_i$ accounts for the fact that we can remove it from anywhere in the string and the factor $n_i-1$ accounts for the fact that we can split up any of the $n_i-1$ instances of the $i$-th letter. The initial values are $a(n_1,\dotsc,-1,\dotsc,n_k)=0$ and $a(0,\dotsc,0)=1$.

For your example, this yields

$$ \begin{eqnarray} a(1,2,1) &=&4a(1,2,0)+a(1,1,0)\\ &=& 4\cdot\frac12a(1,1,0)+a(1,1,0)\\ &=&3a(1,1,0)\\ &=&3\cdot2a(1,0,0)\\ &=&3\cdot2a(0,0,0)\\ &=&6\;, \end{eqnarray} $$

where in each step the recursion was used to reduce the last non-zero letter count.

share|improve this answer
    
I understood my mistake and deleted my wrong answer. –  Tapu Jan 16 '12 at 10:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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