Número de permutaciones con bloques no consecutivos

Question

¿Cuántas cadenas hay formadas exactamente por M A, N B y K C para que no aparezca la cadena BC?

Por ejemplo, cuando M=3, N=1, K=1, $$ABACA$$ cuenta como una cadena válida mientras que $$A\underline{BC}AA$$ no lo hace.

Podemos calcular este valor para valores pequeños de M,N,K forzando manualmente. Pero, ¿hay alguna forma de generalizar esto para valores mayores de M,N y K?

He intentado utilizar la recursión. Dejemos que $a_{m,n,k}$ sea la respuesta para m,n,k. La recursión que une $a_{m+1,n,k}$ a $a_{m,n,k}$ es fácil -_- $$a_{m+1,n,k}= (m+k+n+1)a_{m,n,k}$$ Porque a cada secuencia válida formada por M A's, N B's, K C's, podemos añadir otra A en cualquiera de las M+N+k+1 posiciones. No he podido relacionar $a_{m,n+1,k}$ a $a_{m,n,k}$ . Bueno, es obvio que $a_{m,n,k}= a_{m,k,n}$ , por lo que si somos capaces de vincular $a_{m,n+1,k}$ a $a_{m,n,k}$ se acabará. Ahí es donde estoy atascado.

He encontrado una parte de una recursión todavía- a cada secuencia que consiste en M A's, N B's, K C's, podemos añadir otra B a cualquier otra B, así $a_{m, n+1, k}= n \times a_{m,n,k} + \text{something}$ . Encontrando esto $\text{something}$ es donde estoy atascado en- que $\text{something}$ debe dar cuenta de las cadenas que tienen una B al final. Ahí es donde estoy atascado. ¿Puede alguien ayudarme con mi enfoque?

P.D. Nunca he afirmado que mis declaraciones anteriores sean ciertas. Puede que me haya equivocado, así que también me alegraré si alguien lo señala.

Answer 1

En caso de que todavía quiera la respuesta:

Estos problemas pueden resolverse utilizando un grafo dirigido, y para este problema, el grafo puede escribirse como

\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*}

donde los pesos son las variables de su función generadora, que puede derivarse calculando $(I-A)^{-1}$ y tomando la suma de la primera fila.

La forma simplificada viene dada entonces por:

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

y utilizando el polinomio característico de $A$ la relación de recurrencia se puede escribir como

\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*}