Relación de recurrencia para encontrar cadenas ternarias de longitud $n$ que no contengan $3$ consecutivos $0$ o $2$ consecutivo $1$ 's

Question

OK mi idea es que el número total de posibles cadenas ternarias de longitud $n$ es $3^n$ de las que debo restar las cadenas que contienen $000$ s más las cadenas que contienen $11$ s, excluyendo el número de duplicados (cadenas que contienen ambos $000$ s y $11$ s).

Secuencia para cadenas que contienen 000s: $$f(n)=3\times f(n-1)+2\times(3^{n-4}-f(n-4))$$ Secuencia para cadenas que contienen 11s: $$f(n)=3\times f(n-1)+2\times(3^{n-3}-f(n-3))$$

Ahora, las cadenas que contienen ambas secuencias: Para $n=5$ obtenemos $2$ ( $00011$ y $11000$ ).

Para $n=6$ obtenemos $12$ y para $n=7$ obtenemos $73$ (simplemente produciendo las permutaciones).

Para $n>5$ entiendo que debemos considerar dos casos diferentes, el primero (o último) $5$ dígitos que forman una secuencia "buena" (es decir, que contiene ambas secuencias), en cuyo caso, los restantes $n-5$ puede ser cualquier cosa (lo que nos da $3^{n-5}$ más combinaciones, o $f(n-1)$ ser "malo".

En este caso, ¿cómo podemos distinguir si sólo contiene $000$ s o $11$ s o ninguno de los dos?

En resumen, ¿cómo encontramos la relación de recurrencia para que las cadenas contengan ambos ?

Answer 1

Sea $f(n)$ sea el número de cadenas que empiezan por 0, $g(n)$ el número que empieza por 1, $h(n)$ el número que empieza por 2.

Tenemos $f(n+1)=g(n)+h(n)+g(n-1)+h(n-1)$ (nos. de partida 01,02,001,002 resp).

$g(n+1)=f(n)+h(n)$ (nos. de partida 10,12 resp).

$h(n+1)=f(n)+g(n)+h(n)$ (nos. de partida 20, 21, 22 resp).

Subs 2º equ en otros dos que conseguimos:

$f(n+1)=f(n-1)+h(n-1)+h(n)+f(n-2)+h(n-2)+h(n-1)=f(n-1)+f(n-2)+h(n)+2h(n-1)+h(n-2)$ (*) y

$h(n+1)=f(n)+f(n-1)+h(n-1)+h(n)$ y por lo tanto $h(n)=f(n-1)+f(n-2)+h(n-1)+h(n-2)$ (**)

Sustituyendo (**) en (*) obtenemos: $f(n+1)=2h(n)+h(n-1)$ . Subs que en la equ por $h(n+1)$ da $h(n+1)=2h(n-1)+h(n-2)+2h(n-2)+h(n-3)+h(n-1)+h(n)$ o

$h(n+1)=h(n)+3h(n-1)+3h(n-2)+h(n-3)$ .

Tenga en cuenta que $h(n+1)$ es también el número total de cadenas de longitud $n$ - porque es $f(n)+g(n)+h(n)$ .

Así que escribir $t(n)$ para el número total de cadenas de longitud $n$ que tenemos:

$t(n+1)=t(n)+3t(n-1)+3t(n-2)+t(n-3)$ . Es fácil enumerar las posibles cadenas para pequeñas $n$ para obtener $t(1)=3, t(2)=8, t(3)=21, t(4)=55$ .