Relación de recurrencia para el número de cadenas de bits de longitud n que contienen dos 1s consecutivos

Question

Me estoy tirando de los pelos por una pregunta de repaso para mi final de mañana.

Encuentra una relación de recurrencia (y sus condiciones iniciales) para el número de cadenas de bits de longitud n que contienen dos 1s consecutivos.

Este es mi proceso de pensamiento/trabajo, ¿podría alguien ayudarme a descubrir en qué me estoy equivocando?

Sabiendo que una cadena de bits de longitud 0 ó 1 no puede contener dos bits consecutivos de ningún tipo, y que sólo una cadena de bits de longitud 2 (la cadena 11) puede contener dos unos consecutivos, tengo las condiciones iniciales a(0) = 0 , a(1) = 0 y a(2) = 1 . Ahora estoy tratando de encontrar una fórmula para el término a(n+2) .

Sé que hay tres formas para una cadena de bits de longitud n + 2 para tener dos 1s consecutivos:

• Condición X : Ambos n + 1 y n + 2 son 1. count(X) = 2^n porque esto todavía deja n bits que no se han tenido en cuenta.
• Condición Y : Ambos n y n + 1 son 1. count(Y) = 2^n por la misma razón.
• Condición Z : La primera n bits contienen 11 en alguna parte. count(Z) = 4 * a(n) porque la adición de 2 bits a la a(n) cuadruplica el número de cadenas posibles.

Dado que estas tres condiciones no son mutuamente excluyentes,

a(n+2) = count(X) + count(Y) + count(Z) - (count(X ∩ Y) + count(X ∩ Z) + count(Y ∩ Z)) + count(X ∩ Y ∩ Z)

o

a(n+2) = 2^n + 2^n + 4 * a(n) - (2^(n-1) + a(n) + 2 * a(n-1)) + a(n-1)

Esto demuestra con éxito la condición inicial a(2) = 1 y el siguiente - a(3) = 3 . Pero cuando introduzco 4, obtengo 9. Al enumerar las posibles cadenas a mano y rodear las que satisfacen la condición, sólo obtengo 8. ¿Qué estoy haciendo mal?

Gracias.

Answer 1

He aquí una forma alternativa de resolver tu pregunta.

Dejemos que $a_n$ sea el número de cadenas de bits de longitud $n$ que contiene un par de $1$ 's. Para construir una cadena de bits de este tipo, se podría empezar con

• $0$ y seguir con una cadena de longitud $(n-1)$ que contiene un par de $1$ 's
• $10$ y seguir con una cadena de longitud $(n-2)$ que contiene un par de $1$ 's
• $11$ y seguir con cualquier cadena de longitud $(n-2)$ que contiene un par de $1$ 's

Dado que estos tres casos son mutuamente excluyentes y agotan las posibilidades de cómo podría comenzar dicha cadena, podemos aplicar la regla de la suma y escribir la siguiente relación de recurrencia válida para todo $n \ge 2;$

$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$

(Recordemos que hay $2^k$ cadenas de bits sobre la longitud $k$ ).

Ahora las condiciones iniciales:

• $a_0 = 0$
• $a_1 = 0$

Answer 2

Una forma quizá menos complicada de resolver el problema es dejar que $b_n$ sea el número de la longitud $n$ cadenas de bits con no consecutivos $1$ 's. Es fácil demostrar que $$b_{n+2}=b_{n+1}+b_n.$$ Desde $b_k=2^k-a_k$ La sustitución y una pequeña simplificación dan como resultado $$a_{n+2}=a_{n+1}+a_n+2^n.$$

Answer 3

Su cuenta de $Y \cap Z$ requiere que los dos $1$ 's en $Z$ estar en la primera $n-1$ bits. Para $n=4$ no incluye $001110$