1
$\begingroup$

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.

  • 0
    @joriki I have clarified that i am looking for a closed form answer to this question.2012-01-16

1 Answers 1

1

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.

  • 0
    I understood my mistake and deleted my wrong answer.2012-01-16