Relación de recurrencia para el número de cadenas ternarias que contienen dos ceros consecutivos

Question

La pregunta es: Encontrar una relación de recurrencia para el número de cuerdas ternarias de longitud n que contienen dos ceros consecutivos.

Sé que para las cuerdas ternarias de longitud uno, hay 0. Para una longitud de 2, hay sólo 1 (00), y para una longitud de 3, hay 5 (000,001,002,100,200).

Hice un problema similar, encontrando una relación para el número de cadenas de bits de longitud n con dos ceros consecutivos: $$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$$

Ya que puedes añadir "1" al final de todos los $a_{n-1}$ cuerdas, "10" a todas las $a_{n-2}$ cuerdas, y "00" cualquier cuerda de tamaño $n-2$ .

Para el problema de la cuerda ternaria, estoy bastante seguro de que reemplazarías el $2^{n-2}$ con $3^{n-2}$ pero confundido sobre los otros términos de la relación. Mi conjetura es que tendría el coeficiente $2$ delante de los otros términos, ya que se puede añadir $1$ o $2$ hasta el final de $a_{n-1}$ y o bien $01$ o $02$ al final de $a_{n-1}$ .

Así que creo que la respuesta para la relación es: $$a_n = 2a_{n-1} + 2a_{n-2} + 3^{n-2}$$

¿Cómo se ve eso?

Answer 1

Si una cadena ternaria "buena" de longitud $n$ termina en $00$ El primer $n-2$ Los elementos pueden ser cualquier cosa, por lo que hay $3^{n-2}$ tales cuerdas. Si una buena cadena de longitud $n$ termina en $1$ o $2$ su subcadena inicial de longitud $n-1$ debe ser bueno; eso explica $2a_{n-1}$ más cadenas buenas de longitud $n$ ya que cada una de las cadenas más cortas puede ampliarse con $1$ o $2$ . ¿Qué no se ha contado? Buenas cadenas de longitud $n$ que terminan en un $10$ o $20$ . Cada una de ellas debe ser una extensión de una cadena buena de longitud $n-2$ , por lo que hay $2a_{n-2}$ de ellos, y su conjetura es correcta: $$a_n=2a_{n-1}+2a_{n-2}+3^{n-2}\;.$$

Answer 2

También se puede obtener una fórmula explícita directamente, invocando cadenas de Markov / autómatas finitos deterministas.
Este es el DFA que acepta las cadenas sobre $\Sigma=\{0,1,2\}$ con al menos dos veces consecutivas $0$ s:

Su matriz de transición viene dada por $$ P = \begin{pmatrix}2& 1 & 0 \\ 2 & 0 & 1 \\ 0 & 0 & 3 \end{pmatrix} $$ y el polinomio característico de esta matriz es $(x-3)(x^2-2x-2)$ . Se deduce que el número de cadenas sobre $\Sigma$ con una longitud $n$ y que contenga al menos dos $0$ es $$ L_n = A\cdot 3^n + B\cdot (1+\sqrt{3})^n + C \cdot (1-\sqrt{3})^n $$ para algunas constantes $A,B,C$ que se puede encontrar por interpolación. Dado que $L_1=0, L_2=1$ y $L_3=5$ $$\boxed{L_n=3^n-\left(\tfrac{1}{\sqrt{3}}+\tfrac{1}{2}\right)(1+\sqrt{3})^n+\left(\tfrac{1}{\sqrt{3}}-\tfrac{1}{2}\right)(1-\sqrt{3})^n\;}$$ que cumple claramente la relación de recurrencia mencionada por Brian Scott.

Answer 3

Contemos el número de cadenas $a_n$ que no contienen $00$ como una subcadena. El número requerido de cadenas que contienen $00$ es $3^n - a_n$ .

Llamemos a una cadena que no contiene $00$ tan bueno. Deja que $x_n, y_n, z_n$ sea el número de cadenas buenas de longitud $n$ que terminan con $0, 1, 2$ respectivamente. Claramente, \begin{align*} x_{n+1} &= y_n + z_n \\ y_{n+1} &= x_n + y_n + z_n \\ z_{n+1} &= x_n + y_n + z_n \end{align*} Así, \begin{align*} y_n = z_n, \qquad x_{n+1} = 2y_n, \qquad y_{n+1} = x_n + 2y_n \end{align*} y $y_n$ satisface la recurrencia $y_{n+1} - 2y_n - 2y_{n-1} = 0$ . Las raíces características son $1 \pm \sqrt{3}$ y $$y_n = A(1+\sqrt{3})^n + B(1-\sqrt{3})^n$$ donde $A, B$ son constantes. Como $y_2 = 3$ y $y_3 = 8$ obtenemos $$A = \frac{1+\sqrt{3}}{4\sqrt{3}}, \qquad B=-\frac{1-\sqrt{3}}{4\sqrt{3}}$$ Por lo tanto, $$y_n = \frac{1}{4\sqrt{3}}\left(\alpha^{n+1} -\beta^{n+1}\right) $$ Desde $a_n = x_n + y_n + z_n = 2y_{n-1} + 2y_n$ obtenemos \begin{align*} a_n &= \frac{1}{2\sqrt{3}}\left(\alpha^n(1+\alpha) - \beta^n(1+\beta)\right)\\ &= \left(\frac{2+\sqrt{3}}{2\sqrt{3}}\right)\alpha^n - \left(\frac{2-\sqrt{3}}{2\sqrt{3}}\right)\beta^n \end{align*} Por lo tanto, el número de secuencias de longitud $n$ que contienen $00$ es $$3^n - \left(\frac{2+\sqrt{3}}{2\sqrt{3}}\right)(1+\sqrt{3})^n + \left(\frac{2-\sqrt{3}}{2\sqrt{3}}\right)(1-\sqrt{3})^n$$