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