Deje $t_n$ ser el número de los distintos vectores $T$ de la longitud de la $n$ que se puede hacer usando el proceso anterior. Aquí me limitaré a ofrecer un límite superior en $t_n$. Que es $t_n \leq 2F_{n + 2}$ donde $F_n$ $n^{th}$ Fibonnaci número. En primer lugar, algunas definiciones, a continuación, una prueba.
Definición (formato Comprimido): Para cualquier vector $U$ cuyos elementos son en $\{0, 1\}$, se puede escribir es una forma comprimida $C$ como sigue: $u_0[c_1, c_2, \dots, c_m]$. Aquí $u_0$ es el plazo inicial, y cada una de las $c_i$ es un no-cero número natural que representa una ejecución contigua de $0$ o $1$. Nota en particular de que $m \leq n$ siempre. Por ejemplo, la secuencia de $(0, 1, 1, 1, 0, 0, 1)$ sería representado como $0[1, 3, 2, 1]$.
Prueba (de límite superior): Bien, de acuerdo con el lema de abajo, sabemos que la forma comprimida $C$ de cualquier vector $T$ sólo puede tener $c_i$ términos son todos impares, excepto, posiblemente, el primer y último términos. También, el término es $0$. También es claro que la suma de $c_1 + c_2 + \dots + c_m = n$, a partir de la definición de un comprimido de secuencia. De otra parte, se puede demostrar que el número de secuencias impares añadir algún número $n$$F_{n + 2}$. Ahora, si nos relajar esta restricción para que el primer y/o último término puede ser, incluso, tenemos cuatro posibilidades para el primer/último término: aun/incluso, par/impar, par/impar, impar/impar. Restando 1 a partir de un no-cero, incluso el número siempre nos da un número impar, por lo que el número de arriba de las combinaciones anteriores se $F_{n - 2}, F{n - 1}, F{n - 1}, F_{n}$. Sumando estos y el uso del estándar de Fibonnaci recurrencia da $F_{n + 2}$. Ahora, el primer término de un comprimido secuencia puede ser $1$ o $0$, con lo que conseguimos $2F_{n + 2}$ de un límite superior, según sea necesario.
Lema: La forma comprimida de cualquier vector $T$, construido como en la pregunta, contiene todos los números impares, excepto en su primer y último términos. A ver por qué este es el caso, considere algunos de mediano plazo $k$ en la forma comprimida. Esto corresponde a una ejecución $T_{i + 1}, T_{i + 2}, \dots, T_{i + k}$, $T_{i + k + 1} = T_{i} \neq T_{i + 1}$ $T_{i + j} = T_{i + h}$ todos los $1 \leq j, h \leq k$. Es decir, corresponde a $k$ una sub-secuencia de $k$ igualdad de condiciones en una fila, y los dos términos diferentes, inmediatamente antes y después de la secuencia, que en sí son iguales. Ahora, supongamos $k$ es incluso, hacia una contradicción. Así, considere la posibilidad de la $S$ vector que creó el $T$ vector. Observe que para cualquier $a$, $S_{a + 1} = S{a} \pm2$. También tenga en cuenta que$T_i \neq T_{i + 1}$, por definición. Ahora defina $D_a = \frac{S_{i + a} - Si}{2}$. Nos muestran, de manera inductiva, que por extraño $a$, este valor es impar, y aún por $a$ es incluso. Esto es claramente cierto para $a = 0$. Para el caso inductivo $a = n + 1$, sabemos que $S_{n + 1} = S_{n}\pm2$. Por lo $D_{n + 1} = D_n\pm1$. Por lo que la paridad de $D_n$ claramente se alterna entre términos sucesivos. Ahora, hemos asumido un $k$. Lo que significa que $D_k$ debe ser par, y $D_{k + 1}$ impar. Así que, a continuación,$S_{i + k + 1} \neq S_i$. Pero por la definición de la forma comprimida, $T_{i + k + 1} = T_i$. La única manera en que esto es posible, a partir de la definición de $T$, es si $S_{i + k + 1} = S_{i} - 2$ $S_i \leq 0$ o $S_{i + k + 1} = S_{i} + 2$$S_i > 0$. Pero ambos de estos casos implican que $T_{i + k} = T_{i + k + 1}$, lo cual es una contradicción, por lo $k$ no se puede aún.
Lema (*): Para $u \in \{0, 1\}$ cada vector, que en forma comprimida está escrito $u[1, 1, \dots, 1]$, es construible con el proceso anterior. Para prueba de ello, considere primero el caso de $u = 0$. Entonces podemos ver que el vector $V = (1, -1, 1, -1, \dots)$ da como resultado un vector $T = (0, 1, 0, 1, \dots)$. Esto es debido a que el vector asociado $S$ será $(0, 2, 0, 2, \dots)$ o $(-1, 1, -1, 1, \dots)$, dependiendo de la paridad de la longitud. Para el caso de $u = 1$, el vector $V = (-1, 1, -1, 1, \dots, -1, -1)$ o $V = (-1, 1, -1, 1, \dots, -1)$ va a trabajar. Esto es debido a que el asociado $S$ vector será la $(2, 0, 2, 0, \dots)$ o $(1, -1, 1, -1, \dots)$, de nuevo dependiendo de la paridad de longitud.
Lema (**): Todos los vectores en forma comprimida $C = u[c_1, c_2, \dots, c_m]$ son construibles con el proceso anterior, siempre que todos los $c_i$ son impares. Podemos demostrar esto por inducción en $n$, la longitud del vector original $V$. Empezamos con dos de la base de casos $n = 1, 2$, por lo que podemos saltar por dos en el caso inductivo. Así, se observa que ambos caso obtenemos que todos los $c_i$ que se extraña implica a todos los $c_i = 1$, y por tanto, por (*) hemos terminado.
Para el caso inductivo, de nuevo, si todos los $c_i = 1$, entonces podemos aplicar (*) y hemos terminado. Otra cosa que hay algunos $c_i \geq 3$. Pero entonces, por inducción de la forma comprimida $u[c_1, c_2, \dots, c_i - 2, \dots, c_m]$ puede ser construida. Ahora, mira a los asociados de vectores $T$ que los resultados en esta forma comprimida. El plazo $c_i - 2$ en el comprimido vector corresponde a $c_i - 2$ $0$s o que muchos de los $1s$ en una fila. En cualquier caso, podemos extender esto a $c_i$ $0$s o $1$s mediante la adición de $(-1, 1)$ o $(1, -1)$ en la ranura correspondiente en el vector correspondiente a $V$. Haciendo esto preserva el otro $c_i$, y así lograr nuestro deseado $C$.
Corolario (límite inferior): Un límite inferior para $t_n$$2F_n$. Que es $2F_n \leq t_n$. Esto es debido a que el número de vectores de números impares sumando $n$ $F_n$ (como se muestra en otros lugares), y el inicio término en la forma comprimida puede ser $0$ o $1$.
Poniendo todo junto, tenemos: $2F_n \leq t_n \leq 2F_{n + 2}$.
