The problem is to calculate the number of all unique permutations of a string with repetitions. There is also a constraint for one subset elements to be spaced from each other.
Typical input data is AAAAAABBBCCCC. Lets assign to L the length of input string.
The goal is to find the number of all possible permutations of this string, in which any two C's must not to be placed next each other.
As I understand, the problem can be splitted into 2 subproblems:
- Count number of unique permutations of AAAAAABBB (N1);
- Count number of correct possible placements of all (4 in our case) C's in L (N2);
- Multiply N1 and N2 to get the answer.
N1 can be calculated as:
L!/(La! * Lb!).
How should I calculate N2? I'm not interested in direct answer, just looking for some clarification. My attempt on manual synthesis of the formula was very awful (because we have multiple intervals, and at every element task splits into two).
Do this kind of task is likely to be solved by dynamic programming?
Thanks in advance!
Let's say we have a string of $m$ $A$'s and $n$ $B$'s into which we wish to insert $k$ $C$'s such that no two $C$'s are consecutive. As you correctly concluded, there are $\binom{m + n}{n}$ strings of $m$ $A$'s and $n$ $B$'s. The $k$ $C$'s can be inserted in the $m + n - 1$ spaces between consecutive letters of the string of $m$ $A$'s and $n$ $B$'s or in the two spaces at the end of the string, giving us $m + n - 1 + 2 = m + n + 1$ spaces where we can place the $k$ $C$'s. Thus, we can place the $C$'s in $\binom{m + n + 1}{k}$ ways. Note that if $k > m + n + 1$, $\binom{m + n + 1}{k} = 0$, as we would expect since using more than $m + n + 1$ $C$'s would require us to use at least two consecutive $C$'s. Hence, there are $$\binom{m + n}{n}\binom{m + n + 1}{k}$$ strings with $m$ $A$'s, $n$ $B$'s, and $k$ $C$'s in which no two $C$'s are consecutive.