Relación de recurrencia para secuencias binarias

Question

¿Cómo puedo encontrar la relación de recurrencia con a) ningún bloque de 2 0's consecutivos y b)ningún bloque de 3 0's consecutivos.

Por favor, ayúdenme a entender este material, una explicación detallada será muy apreciada, Gracias

Answer 1

No tratamos con $3$ consecutivo $0$ . El mismo enfoque funcionará para no $2$ consecutivos $0$ pero es más sencillo.

Sea $a_n$ sea el número de cadenas binarias de longitud $n$ sin $3$ consecutivo $0$ . Esta cadena se denomina bien cuerda. Sea $n\gt 3$ .

Una buena $n$ -cadena con $n\gt 3$ pueden ser de tres tipos:

Tipo 1: termina en $1$ .

Tipo 2: termina en solo $0$

Tipo 3: termina en doble $0$ .

Tipo 1: Podemos hacer un buen $n$ -de tipo 1 añadiendo una cadena $1$ a un buen $(n-1)$ -cadena. Y todos los Tipo 1 bueno $n$ -se obtienen de este modo. Por lo tanto, hay exactamente tantos buenos Tipo 1 $n$ -cuerdas como hay buenas $(n-1)$ -cuerdas. Por definición existen $a_{n-1}$ de estos.

Tipo 2: Una buena cadena de longitud $n\gt 3$ que termina en un único $0$ debe terminar en $10$ . Así se obtiene de una buena $(n-2)$ -cadena añadiendo $10$ a ella. Así que hay tantos buenos Tipo 2 $n$ -cuerdas como hay buenas $(n-2)$ -cuerdas. Por definición, existen $a_{n-2}$ de estos.

Tipo 3: Una buena cadena de longitud $n\gt 3$ que termina en $00$ debe terminar en $100$ . Así se obtiene de un buen $(n-3)$ -cadena añadiendo $100$ a ella. Así que hay tantos buenos Tipo 3 $n$ -cuerdas como hay buenas $(n-3)$ -cuerdas. Por definición, existen $a_{n-3}$ de estos.

De ello se deduce que si $n\gt 3$ entonces $$a_n=a_{n-1}+a_{n-2}+a_{n-3}.$$