Encuentre una relación de recurrencia para el número de cadenas ternarias de longitud ݊ que no contienen dos 0s consecutivos y dos 1s consecutivos.

Question

Encontrar una relación de recurrencia para el número de ternario cadenas de longitud ݊ que no contienen dos 0s consecutivos o dos días consecutivos de 1s.

Esta pregunta de arriba tiene una relación de recurrencia $f_{n}=2f_{n-1}+f_{n-2}$ pero el mismo problema de la sustitución de o a y:

Encontrar una relación de recurrencia para el número de ternario cadenas de longitud ݊ que no contienen dos días consecutivos de 0s y dos consecutivos 1s.

Traté de resolverlo de la manera siguiente:

i) se inicia con 2 -> $a_{n-1}$

ii) se inicia con 12 o 02 -> $a_{n-2}$

iii) se inicia con el 012 o 102 -> $a_{n-3}$

y así sucesivamente .

Así la relación : $$f_{n}=f_{n-1}+2f_{n-2}+2f_{n-3}+....+f_{0}+2$$ que es $$f_{n}=2f_{n-1}+f_{n-2}$$ Recibí una misma relación como o. Por favor me ayudan a saber donde ¿qué hice mal?

Answer 1

Así que el problema, como yo lo veo, se inicia poco después de punto (iii) anterior: ¿qué acerca de las cadenas que comienzan con 002? Para encontrar esos casos, usted debe encontrar cadenas de longitud $n-3$ que no tiene 11 en ellos. Esta es una cantidad menor que $a_{n-3}/2$, pero, ¿cuánto no sé. (el 112 caso es similar)

Así, para resolver esto, me gustaría dividir el problema en varias clases, encontrar una relación de recurrencia para cada clase, y luego se combinan para obtener una recurrencia de la suma.

Entonces, vamos a definir un par de casos:

$a_n$ será la secuencia original, el número de trinarias cadenas de longitud $n$ que no contienen dos días consecutivos de 0s y dos consecutivos 1s
$b_n$ será el número de trinarias cadenas de longitud $n$ que hacer contienen dos 0s consecutivos, pero no contienen dos consecutivos 1s
$c_n$ será el número de trinarias cadenas de longitud $n$ que hacer contienen dos consecutivos 1s, pero no contienen dos consecutivos 0s
$d_n$ será el número de trinarias cadenas de longitud $n$ que no contengan cualquiera de los dos 0s consecutivos o dos días consecutivos de 1s

Tenga en cuenta que $a_n = b_n + c_n + d_n$.

Ahora, para $i = 0, 1, 2$, vamos a $a^i_n$ ser las cadenas de ser las cadenas de la clase que estamos buscando para contar a hacer $a_n$ que comienzan con un dígito $i$. Así, por ejemplo, tenemos: $$a_n = a^0_n + a^1_n + a^2_n$$ Del mismo modo, definir $b^i_n$, $c^i_n$, y $d^i_n$.

Ahora, considere la posibilidad de encontrar una relación de recurrencia para $b_n$; es más fácil de romper que en relaciones de recurrencia para $b^0_n$, $b^1_n$, y $b^2_n$.

Recta de las definiciones, se obtiene: $$\begin{align} b^0_n &= b_{n-1} + d^0_{n-1} \\ b^1_n &= b^0_{n-1} + b^2_{n-1} \\ b^2_n &= b_{n-1} \end{align}$$ Recuerde, estamos buscando cadenas que hacer contengan 00 pero no contienen 11. Para dicha cadena para comenzar con 0, lo que significa que el resto de la cadena ya ha cumplido con nuestra condición de ($b_{n-1}$ de los casos) o una cadena de caracteres sin consecutivos 0s o 1s consecutivos que se inició con 0 ($d^0_{n-1}$ de los casos). Para dicha cadena para comenzar con 1, lo que significa que el resto de la cadena ya ha cumplido con nuestra condición y comenzó con un 0 o 2 ($b^0_{n-1} + b^2_{n-1}$ de los casos). Para dicha cadena para comenzar con 2, sólo significa que el resto de la cadena coincidente nuestra condición. ($b_{n-1}$ de los casos)

Para reducir el número de serie de la que estamos tratando, vamos a tratar de eliminar la serie $b^i_n$ y dejarnos sólo con $b^i_n$ e $d^0_n$ en los lados de la parte derecha:

$$\begin{align} b^0_n &= b_{n-1} + d^0_{n-1} \\ b^1_n &= b_{n-2} + d^0_{n-2} + b_{n-2} \\ b^2_n &= b_{n-1} \end{align}$$

Por lo tanto: $$b_n = b^0_n + b^1_n + b^2_n = 2b_{n-1} + 2b_{n-2} + d^0_{n-1} + d^0_{n-2}$$ Por una lógica similar, se puede derivar una fórmula para $c_n$: $$c_n = 2c_{n-1} + 2c_{n-2} + d^1_{n-1} + d^1_{n-2}$$

Note that we already have a a recurrence relation for $d_n$ del problema original: $$d_n = 2d_{n-1} + d_{n-2}$$

Also note that $d^2_n = d_{n-1}$ y por lo tanto $$d^0_n + d^1_n = d_n - d^2_n = d_n - d_{n-1}$$ Esto será muy útil más adelante.

Ahora bien, para $a_n$: $$\begin{align} a_n &= b_n + c_n + d_n \\ &= 2b_{n-1} + 2b_{n-2} + d^0_{n-1} + d^0_{n-2} \\ & \qquad + 2c_{n-1} + 2c_{n-2} + d^1_{n-1} + d^1_{n-2} \\ & \qquad + 2d_{n-1} + d_{n-2} \\ &= 2a_{n-1} + a_{n-2} + (a_{n-2} - d_{n-2}) + d_{n-1} - d_{n-2} + d_{n-2} - d_{n-3} \\ &= 2a_{n-1} + 2a_{n-2} + d_{n-1} - d_{n-2} - d_{n-3} \\ &= 2a_{n-1} + 2a_{n-2} + (2d_{n-2} + d_{n-3}) - d_{n-2} - d_{n-3} \\ &= 2a_{n-1} + 2a_{n-2} + d_{n-2} \end{align}$$

Casi allí. Ahora podemos trabajar para eliminar la $d_{n-2}$ términos, pero el primer aviso de que esta última ecuación puede escribirse como: $$d_{n-2} = a_n - 2a_{n-1} - 2a_{n-2}$$ Y por lo tanto estas dos ecuaciones siguientes: $$\begin{align} d_{n-3} &= a_{n-1} - 2a_{n-2} - 2a_{n-3} \\ d_{n-4} &= a_{n-2} - 2a_{n-3} - 2a_{n-4} \end{align}$$ Ahora, la aplicación de la relación de recurrencia para $d_n$ nuevo: $$\begin{align} a_n &= 2a_{n-1} + 2a_{n-2} + d_{n-2} \\ &= 2a_{n-1} + 2a_{n-2} + 2d_{n-3} + d_{n-4} \\ &= 2a_{n-1} + 2a_{n-2} + 2a_{n-1} - 4a_{n-2} - 4a_{n-3} + a_{n-2} - 2a_{n-3} - 2a_{n-4} \\ &= 4a_{n-1} - a_{n-2} - 6a_{n-3} - 2a_{n-4} \end{align}$$ Así que ese es el final de la recurrencia de la relación: $$a_n = 4a_{n-1} - a_{n-2} - 6a_{n-3} - 2a_{n-4}$$ Esto es algo de un desastre, sino que se comprueba: $$\begin{align} a_0 &= 1 \\ a_1 &= 3 \\ a_2 &= 9 \\ a_3 &= 27 \\ a_4 &= 79 \\ a_5 &= 229 \\ a_6 &= 657 \\ a_7 &= 1871 \\ a_8 &= 5295 \end{align}$$

Los valores fueron calculados con la recurrencia de la relación y verificado por el programa en python:

import itertools
def find_a_sub_n(n):
    c = 0
    for q in itertools.product(*([['0','1','2']]*n)):
        h = ''.join(q)
        if not (('11' in h) and ('00' in h)):
            c = c+1
    return c

Answer 2

Nota: Inspirado por la bonita respuesta de @DanielMartin ofrecemos un enfoque ligeramente diferente. Sin embargo, también llevará a la misma lineal de la recurrencia de la relación. De hecho, hay algunos argumentos que indican que no más simple lineal de la recurrencia de la relación puede ser encontrado.

Con el fin de facilitar la comparación puedo usar la misma notación @DanielMartin.

Consideremos los siguientes conjuntos de palabras construido a partir de la ternario alfabeto $V=\{0,1,2\}$.

• $a_n$: Cuenta el ternario palabras que no contienen tanto $00$ así como de $11$

• $d_n$: Cuenta el ternario palabras que no contienen cualquiera de las $00$ o $11$ o ambos.

• $e_n$: Cuenta el ternario palabras que no contengan $00$.

• $f_n$: Cuenta el ternario palabras que no contengan $11$.

Las variables obedece a la siguiente relación $$\begin{align*} a_n=e_n+f_n-d_n \end{align*}$$

En efecto, desde el $e_n$ cuenta las palabras sin consecutivas $0$'s y $f_n$ las palabras sin consecutivas $1$'s el número de palabras que no contienen ninguna de ellas, ni $00$ ni $11$, dado por $d_n$ es contada dos veces. Esto es compensado por restando $d_n$.

Nota, la conexión con $b_n$ e $c_n$ en la respuesta por @DanielMartin está dada por $$\begin{align*} e_n&=c_n+d_n\\ f_n&=b_n+d_n\\ \end{align*}$$

La recurrencia de la relación de $d_n$ e $e_n$:

Debido a la simetría podemos ver que $e_n=f_n$ y obtenemos $$\begin{align*} a_n=2e_n-d_n\tag{1} \end{align*}$$ Denotando con $e_n^i$ una palabra contada por $e_n$ que comienza con $i\in\{0,1,2\}$. Se obtiene una relación de recurrencia para $e_n$ por $$\begin{align*} e_n^0&=e_{n-1}^1+e_{n-1}^2\tag{2}\\ e_n^1&=e_{n-1}\tag{3}\\ e_n^2&=e_{n-1}\\ \end{align*}$$

Comentario:

• Obtenemos (2), ya que las palabras de longitud $n$ sin consecutivas $0$'s que comienzan con $0$ son seguidos por las palabras de longitud $n-1$ que tiene que empezar con $1$ o $2$.
• En (3) se nota que las palabras de longitud $n$ sin consecutivas $0$'s que comienzan con $1$ son seguidos por las palabras de longitud $n-1$ sin consecutivas $0$'s. El mismo es debido a la simetría también para $e_n^2$.

Obtenemos $$\begin{align*} e_n&=e_n^0+e_n^1+e_n^2\\ &=(e_{n-1}^1+e_{n-1}^2)+(e_{n-1})+(e_{n-1})\\ &=(e_{n-2}+e_{n-2})+2e_{n-1}\\ &=2e_{n-1}+2e_{n-2}\tag{4} \end{align*}$$

Del mismo modo obtenemos una relación de recurrencia para $d_n$ por $$\begin{align*} d_n&=d_n^0+d_n^1+d_n^2\\ &=(d_{n-1}^1+d_{n-1}^2)+(d_{n-1}^0+d_{n-1}^2)+d_{n-1}\\ &=2d_{n-1}+d_{n-1}^2\\ &=2d_{n-1}+d_{n-2}\tag{5} \end{align*}$$

La recurrencia de la relación de $a_n$:

Ahora nos derive una relación de recurrencia para $a_n$. Podemos obtener a partir de (1) $$\begin{align*} a_n&=2e_n-d_n\\ a_{n-1}&=2e_{n-1}-d_{n-1}\\ a_{n-2}&=2e_{n-2}-d_{n-2}\\ \end{align*}$$

Se sigue con (4) y (5)

$$\begin{align*} a_n&=2e_n-d_n\tag{6}\\ &=4e_{n-1}-4e_{n-1}-d_n\\ &=2a_{n-1}+2d_{n-1}+2a_{n-2}+2d_{n-2}-d_n\\ &=2a_{n-1}+2a_{n-2}+d_{n-2} \tag{7} \end{align*}$$

Casi no hay - para usar las palabras de @DanielMartin. Esta relación (7) también fue encontrado en su respuesta y de él deriva finalmente, a partir de la relación $$\begin{align*} a_n = 4a_{n-1} - a_{n-2} - 6a_{n-3} - 2a_{n-4}\qquad\qquad n\geq 4\tag{8} \end{align*}$$

Ahora, además, echa un vistazo a las funciones de generación de $e_n$ e $d_n$. Esto dará otro punto de vista a la recurrencia de la relación. Empezamos con una generación de la función de las palabras de una de tres caracteres del alfabeto que cuenta las palabras sin iguales y consecutivas de caracteres. Estas palabras se llaman Smirnov o Carlitz palabras. Ver (ejemplo III.24 Smirnov palabras de la Analítica de la Combinatoria de Philippe Flajolet y Robert Sedgewick para obtener más información.

La generación de la función $G(z)$ dando el número de Smirnov palabras de más de tres caracteres del alfabeto es $$\begin{align*} G(z)=\left(1-\frac{3z}{1+z}\right)^{-1} \end{align*}$$

Funciones de generación de $e_n$ e $d_n$

Para obtener una generación de función $E(z)=\sum_{n\geq 0}e_nz^n$ para los tres caracteres de palabras sin consecutivas $0$'s podemos tomar todos Smirnov palabras y sustituir cada ocurrencia de $1$ con una o más ocurrencias de $1$ e la misma con $2$. Esto significa en términos de la generación de funciones de sustitución de $z$ con $\frac{z}{1-z}$. Obtenemos de acuerdo a la que se refiere la sección $$\begin{align*} E(z)&=\left(1-\frac{z}{1+z}-\frac{\frac{2z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}\\ &=\left(1-\frac{z}{1+z}-2z\right)^{-1}\\ &=\frac{1+z}{1-2z-2z^2}\\ &=1+3z+8z^2+22z^3+60z^4+164z^5+\cdots \end{align*}$$

La secuencia de $e_n$ está archivado en OEIS como A028859

De forma análoga se obtiene la generación de la función $D(z)=\sum_{n\geq 0}d_nz^n$ para los tres caracteres sin consective $0$'s, así como no consecutivas $1$, obtenemos $$\begin{align*} D(z)&=\left(1-\frac{2z}{1+z}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}\\ &=\left(1-\frac{2z}{1+z}-z\right)^{-1}\\ &=\frac{1+z}{1-2z-z^2}\\ &=1+3z+7z^2+17z^3+41z^4+99z^5+\cdots \end{align*}$$

La secuencia de $d_n$ está archivado en OEIS como A078057

Funciones de generación de $a_n$

De acuerdo a $$a_n=2e_n-d_n$$ stated as (6) we observe that $E(z)$ and $D(z)$ are building blocks for $A(z)=\sum_{n\geq 0}a_nz^n$ $$\begin{align*} A(z)&=2E(z)-D(z)\\ &=\frac{2(1+z)}{1-2z-2z^2}-\frac{1+z}{1-2z-z^2}\\ &=\frac{(1+z)(1-2z)}{1-4z+z^2+6z^3+2z^4}\tag{9}\\ &=1+3z+9z^2+27z^3+79z^4+229z^5+\\ &\qquad+657z^6+1871z^7+5295z^8+14909z^9+\cdots \end{align*}$$

La secuencia de $a_n$ es gracias a @DanielMartin archivados en OEIS como A282087.

A partir de (9) vemos que $$\begin{align*} (1-4z+z^2+6z^3+2z^4)A(z)&=(1+z)(1-2z)\\ \end{align*}$$ Por $n\geq 4$ con $[z^n]$ denota el coeficiente de $z^n$ $$\begin{align*} 0&=[z^n](1-4z+z^2+6z^3+2z^4)A(z)\\ &=[z^n]-4[z^{n-1}]+[z^{n-2}]+6[z^{n-3}]+2[z^{n-4}]\\ &=a_n-4a_{n-1}+a_{n-2}+6a_{n-3}+2a_{n-4} \end{align*}$$ que se corresponde con el de la recurrencia de la relación (8).

Nota: Desde $A(z)=2E(z)-D(z)$ es construido a partir de expresiones que no pueden ser simplificados, esto también se aplica para el lineal de la recurrencia de la relación (8).