\begin {alinear} f(0) &= 1 \\ f(1) &= 2 \\ f(n) &= 2f(n-1)-f(n-2)+ \sigma_0 (n-1) \\ &= 1+n+ \sum_ {i=1}{n-1}i \cdot\sigma_0 (n-i) \end {alinear}
Donde \sigma_0 es la cuenta divisora, A000005 en OEIS. No tengo una prueba formal completa, pero puedo hacer un boceto.
En lugar de mirar todo lo posible P y T vamos a mirar directamente a las posibles secuencias de coincidencia M para enumerarlos. M es siempre una posibilidad si son todos ceros (considere P todos, T todos los ceros). M también es siempre una posibilidad si contiene exactamente una 1 (considera P todos, T todos los ceros excepto una serie de n en la posición correcta).
¿Y si M contiene múltiples 1 s? Si M contiene dos 1 s que son k posiciones separadas, entonces todos P que puede llevar a M tienen para tener período k . Esto es fácil de ver si miramos un ejemplo. Considere M=??1?1??? donde el ? son arbitrarias, es decir. k=2 . Tenemos P=abcdefgh donde el a a h son (independientemente) 0 o 1 . Esos dos 1 s en M imponen una cierta estructura a T :
M ??101???
T = ??abcdefgh????? imposed by first 1
T = ????abcdefgh??? imposed by second 1
De esto, podemos ver que a=c=e=g y b=d=f=h y por lo tanto P necesita tener período 2 .
Ahora bien, desde T tiene longitud 2n-1 todas las restricciones impuestas por la 1 s en M se superponen en al menos una posición. Por lo tanto, el segmento entre la primera 1 y el último 1 tiene que obedecer el mismo período. En otras palabras, la distancia entre dos adyacentes 1 s en un válido M debe ser el mismo. Los ejemplos válidos incluyen 111 y 000100100100000 pero no 1101 , 010010001 o 010101000101 . Smylic lo prueba formalmente en su respuesta .
Con esto en mente, podemos construir una fórmula recursiva o explícita para el número de M , f(n) . Echemos un vistazo a la lista completa de n=4 :
0000 \\ 0001 \\ 0010 \\ 0011 \\ 0100 \\ 0101 \\ 0110 \\ 0111 \\ 1000 \\ 1001 \\ 1010 \\ 1100 \\ 1110 \\ 1111 \\
Siempre podemos generar una M_n (es decir, una secuencia de longitudes que coincidan n ) tomando una M_{n-1} y preparando un cero. Eso nos da los primeros ocho M_4 en la lista anterior. Su número si por supuesto f(n-1) .
También podemos generar una M_n añadiendo un cero, pero tenemos que asegurarnos de que no contamos dos veces con el paso anterior. El M_{n-1} a la que podemos añadir un cero y obtener un nuevo M_n son los que empiezan con un 1 . En otras palabras, aquellos que no eran obtenido de la preparación de un cero. Hay cuatro de estos para M_4 y su número general es f(n-1) - f(n-2) .
Finalmente, hay algunos M_n que empiezan y terminar con 1 . Ya que estamos añadiendo un nuevo 1 tenemos que asegurarnos de que sus distancias son todas iguales. Pero esto es bastante fácil ya que sabemos que el 1 s abarcan todo el n posiciones. Esto significa que debe haber una 1 en cada j la posición, donde j divide n-1 (por ejemplo 1001001 donde hay un 1 en una de cada tres posiciones y 3 divide n-1=6 ). El número de formas en que podemos escribir estos son el número de divisores de n-1 , \sigma_0 (n-1) .
Tomando todo eso en conjunto llegamos a la fórmula recursiva anterior
f(n) = 2f(n-1)-f(n-2)+ \sigma_0 (n-1)
Alternativamente, podemos mirarlo explícitamente: como dije, tener todos 0 Siempre funciona, lo cual es una posibilidad. Tener un solo 1 siempre funciona, lo que nos da n posibilidades. Si hay más de una 1 el 1 s abarcan alguna subcadena de M de longitud 2 \leq i \leq n . Podemos tratar esta subcadena de la misma manera que el último caso de la derivación recursiva y encontrar que hay \sigma_o (i-1) formas de colocar el 1 en esa subcadena. Además, hay n+1-i para colocar esa subcadena en M , rodeada por 0 s, lo que nos da la multiplicidad en la suma:
f(n) = 1+n+ \sum_ {i=1}^{n-1}i \cdot\sigma_0 (n-i)