# Number of permutation with non-consecutive blocks

How many strings are there consisting of exactly M A's, N B's, and K C's so that the string BC does not appear?

For example, when M=3, N=1, K=1, $$ABACA$$ counts as a valid string whereas $$A\underline{BC}AA$$ does not.

We can calculate this value for small values of M,N,K manually brute-forcing. But is there any way to generalize this for larger values of M,N, and K?

I tried using recursion. Let $a_{m,n,k}$ be the answer for m,n,k. The recursion linking $a_{m+1,n,k}$ to $a_{m,n,k}$ is easy -_- $$a_{m+1,n,k}= (m+k+n+1)a_{m,n,k}$$ Because to each valid sequence consisting of M A's, N B's, K C's, we can append another A to any of the M+N+k+1 positions. I have been unable to link $a_{m,n+1,k}$ to $a_{m,n,k}$. Well, it is obvious that $a_{m,n,k}= a_{m,k,n}$, so if we are able to link $a_{m,n+1,k}$ to $a_{m,n,k}$ we will be done. That is where I am stuck.

I have found a part of a recursion still- to each sequence consisting of M A's, N B's, K C's, we can append another B to any other B, so $a_{m, n+1, k}= n \times a_{m,n,k} + \text{something}$. Finding this $\text{something}$ is where I am stuck at- that $\text{something}$ should account for the strings which have a B at the end. That is where I am stuck at. Can anyone help me with my approach?

P.S I never claim my above statements are true. I might have made a mistake, so I will also be glad if anyone points that out.

• Anyone online? :( Commented Oct 9, 2013 at 17:51
• Why don't you think along these lines? Compute the number of strings having at least one "BC" as the sub string. Now, subtract it from the total number of strings. It is simple this way. Isn't it? Commented Oct 9, 2013 at 18:50

In case you still want the answer:

Such problems can be solved using a directed graph, and for this problem, the graph can be written as:

\begin{align*} A &= \begin{array}{|l|rrrr|}\hline & \mathrm{I} & \mathrm{A} & \mathrm{B} & \mathrm{C} \\ \hline \mathrm{I} & 0 & a & b & c \\ \mathrm{A} & 0 & a & b & c \\ \mathrm{B} & 0 & a & b & 0 \\ \mathrm{C} & 0 & a & b & c \\ \hline \end{array} \end{align*}

where the weights are the variables for its generating function, which can be derived by computing $(I-A)^{-1}$ and taking the sum of the first row.

The simplified form is then given by:

\begin{align*} G(a,b,c) &= \frac{1}{1-a-b-c+b\, c} \end{align*}

and by using the characteristic polynomial of $A$, the recurrence relation can be written as;

\begin{align*} f_{m,n,k} &= f_{m-1,n,k}+f_{m,n-1,k}+f_{m,n,k-1}-f_{m,n-1,k-1} \end{align*}

• If you could please elaborate the digraph, would be highly obliged. Commented Oct 6, 2020 at 7:30
• Since C must not appear after B, that edge is not present. And since we won't be going to initial state, those edges are also not present.
– gar
Commented Dec 20, 2020 at 16:18