¿Número de cadenas binarias de longitud n que no contienen una determinada subcadena?

Question

Sea $A_n$ denotan el conjunto de cadenas de elementos del conjunto {0, 1} de longitud $n$ . Sea $B_n$ son las cadenas de $A_n$ que no contengan $0,1,1$ como subcadena (en posiciones consecutivas). Sea $b_n = |B_n|$ .

Demostrar que para $n\geq4$ tenemos $b_n =b_{n1}+b_{n2}+1$ . Además, determine la función generatriz de esta sucesión.

Intenté demostrar la relación de recurrencia en la primera parte mediante inducción, pero me encontré con una situación complicada en la que tenía que considerar el número de subcadenas que empezaban por $1,1$ y eso no me llevó a ninguna parte. Intenté saltarme eso y determinar la función generadora asumiendo que la relación de recurrencia era cierta y obtuve $f(x)=\sum\limits_{n=0}^{\infty}b_nx^n=-\frac{1}{1-x}*\frac{1}{x^2+x-1}$ considerando $f(x)+xf(x)+\frac{1}{1-x}$ pero tampoco estoy seguro de qué hacer con mi resultado.

Tengo la sensación de que se me está escapando alguna idea clave (o quizá sólo esté cometiendo un error tonto de álgebra) en mi trabajo, y me preguntaba cómo podrían abordar otros este problema.

Answer 1

Sea $c_n$ y $d_n$ sea el número de 011 que evitan $n$ -cadenas que terminan en 0 y 1, respectivamente. Entonces $c_0=c_1=d_0=d_1=1$ , $d_2=2$ y, condicionando la longitud $k$ de la última ejecución, vemos que \begin{align} c_n &= \sum_{k=1}^n d_{n-k} &&\text{for $n \ge 1$}\\ d_n &= c_{n-1} + 1 &&\text{for $n \ge 3$} \end{align} Sea $C(z)=\sum_{n=0}^\infty c_n z^n$ y $D(z)=\sum_{n=0}^\infty d_n z^n$ . Entonces las relaciones de recurrencia implican \begin{align} C(z)-1 &= \frac{z}{1-z} D(z) \\ D(z)-1-z-2z^2 &= z(C(z)-1-z) + \frac{z^3}{1-z} \end{align} Resolución de $C(z)$ y $D(z)$ produce \begin{align} C(z) &= \frac{1-z+z^3}{1-2z+z^3}\\ D(z) &= \frac{1}{1-z-z^2} \end{align} La función generadora deseada es entonces (restando $1z_0$ para la cadena vacía que, de lo contrario, se cuenta dos veces) $$C(z)+D(z)-1=\frac{1}{1-2z+z^3}=\frac{1}{(1-z)(1-z-z^2)},$$ que es OEIS A000071 . Obsérvese que el denominador implica la relación de recurrencia $b_n=2b_{n-1}-b_{n-3}$ para $n \ge 3$ .

Answer 2

Como señala lulu en un comentario: En primer lugar, tenga en cuenta que si la cadena binaria termina con $11$ entonces debe consistir enteramente en $1$ 's.

Sea $x_n$ denotan el número de cadenas binarias que terminan en $0$ (que evitan $011$ ).

Sea $y_n$ denotan el número de cadenas binarias que terminan en $01$ (que evitan $011$ ).

Entonces es fácil establecer las siguientes relaciones de recurrencia \begin{eqnarray*} b_n&=&x_n+y_n+1 \\ x_{n+1}&=&x_n+y_n+1 \\ y_{n+1}&=&x_n. \end{eqnarray*} Muele a través del álgebra y tenemos $b_{n}=b_{n-1}+b_{n-2}+1$ .

Ahora multiplica esta ecuación por $x^n$ y suma de $n=2$ hasta $ \infty$ y tenemos \begin{eqnarray*} \sum_{n=2}^{\infty} b_{n} x^n= \sum_{n=2}^{\infty} b_{n-1} x^n+ \sum_{n=2}^{\infty} b_{n-2} x^n+ \sum_{n=2}^{\infty}x^n \\ f(x)-1-2x =x(f(x)-1) +x^2f(x)+\frac{x^2}{1-x}. \end{eqnarray*} Ahora es un hop & skip derivar una fórmula para $f(x)$ .