Contar el número de secuencias coincidentes exactas

Question

Considere todos los pares de cuerdas binarias $P$ y $T$ . Que la longitud de $P$ ser $n$ y la longitud de $T$ ser $2n-1$ . Para cada una de estas parejas, podemos comprobar si $P$ es exactamente igual a cada uno de los $n$ substratos de $T$ en orden de izquierda a derecha y emitir una secuencia que represente estos resultados. Por ejemplo:

$$P = 11011, T = 111011011$$

da una secuencia de salida:

$$01001$$

donde $1$ representa una coincidencia exacta y $0$ representa un desajuste.

Si iteramos sobre todos los pares posibles $P$ , $T$ podemos contar cuántas secuencias distintas obtenemos de las salidas. Para $n = 2, \dots , 9$ tenemos

• $n = 2$ da 4
• $n = 3$ da 8
• $n = 4$ da 14
• $n = 5$ da 23
• $n = 6$ da 34
• $n = 7$ da 49
• $n = 8$ da 66
• $n = 9$ da 87

¿Es posible dar una fórmula para este recuento o alternativamente dar una aproximación asintótica?

Answer 1

Lemma. Deje que $R = R(P, T)$ ser una secuencia de salida para determinadas cadenas $P$ y $T$ de longitud $n$ y $2n - 1$ en consecuencia. Luego $$R = \underbrace {00 \ldots\ldots\ldots\ldots\ldots\ldots0 }_{ \text {non-negative number of zeros}} \underbrace {1 \underbrace {0 \ldots0 }_{ \text {$ k - 1 $ zeros}}1 \underbrace {0 \ldots0 }_{ \text {$ k - 1 $ zeros}}1 \ldots 1 \underbrace {0 \ldots0 }_{ \text {$ k - 1 $ zeros}}1}_{ \text {non-negative number of ones}} \underbrace {00 \ldots\ldots\ldots\ldots\ldots\ldots0 }_{ \text {non-negative number of zeros}}$$ para algún número entero positivo $k$ . (En otras palabras, la distancia entre dos vecinos cualesquiera en $R$ es lo mismo.)

Prueba. Supongamos que $$R = \underbrace { \ldots\ldots\ldots }_{ \text {whatever}}1 \underbrace {00 \ldots0 }_{ \text {$ k - 1 $ zeros}}1 \underbrace {00 \ldots0 }_{ \text {$ \ell - 1 $ zeros}}1 \underbrace { \ldots\ldots\ldots }_{ \text {whatever}}$$ para algunos números enteros positivos $k \ne \ell$ . Deje que $k < \ell$ de lo contrario, podemos revertir todo $P$ , $T$ y $R$ .

Deje que $P = a_0a_1 \ldots a_{n - 1}$ donde $a_i$ son símbolos. Deje que $d = \gcd\ {\,k, \ell\ ,\}$. Luego$$T = T_1P_0P_1 \ldots P_mT_2,$$donde$T_i$y$P_i$son cuerdas tales que$P = P_0 P_1 \ldots P_{x - 1}P'_x$,$|P_0| = |P_1| = \ldots = |P_{m - 1}| = d$,$0 \le |P_m| < d$y$P'_x = P_m$es un prefijo de$P_x$. (Aquí$AB$significa concatenación de cuerdas$A$y$B$ .)

Deje que $K = \frac {k}{d}$ y $L = \frac { \ell }{d}$ . Luego $P_i = P_{i + K}$ para $0 \le i < m - K$ y $P_i = P_{i + L}$ para $0 \le i < m - L$ . También $ \gcd\ {\,K, L\,\} = 1$ .

Así que $P_0 = P_{K} = P_{2K} = \ldots = P_{yK}$ para $(y - 1)K < L \le yK$ . Si $K \mid L$ entonces es fácil ver que $P$ es el prefijo de $P_0P_1 \ldots P_x = P_1P_2 \ldots P_{x+1}$ Por lo tanto $R$ Falta por lo menos un 1. Luego $(y - 1)K < L < yK$ y $P_0 = P_{yK - L} = P_{yK - L + K} = \ldots$ . Iterando este proceso conseguimos $P_0 = P_1 = \ldots = P_{m - 1}$ y $P_m$ es un prefijo de $P_0.$ Por lo tanto $R$ falta por lo menos un 1, y esta contradicción prueba el lema. $\square$

Es fácil ver que cada $R$ descrito en la condición de lemma es alcanzable, por lo que lemma describe todo $R$ posible.

Para calcular el número de tales secuencias es mejor contar las secuencias de todos los 0 y las secuencias con un 1 y luego para todos $k$ encontrar el número de secuencias con al menos dos 1's: $$1 + n + \sum_ {k = 1}^{n - 1} \sum_ {r = 0}^{k - 1} \binom { \left\lceil\frac {n - r}{k} \right\rceil }{2}.$$

Aquí $k$ es la distancia entre unos y otros, $r$ es un resto del número de posición (de base cero) del primer módulo 1 $k$ y $\binom { \left\lceil\frac {n - r}{k} \right\rceil }{2}$ es el número de formas de elegir el primero y el último.

P. S. Es posible mostrar que la asintótica de estas funciones es $\frac12n ^2 \ln n$ . Deje que $f(n)$ sea el número deseado de secuencias. Usando la desigualdad $x \le \lceil x \rceil < x + 1$ tenemos $$1 + n + \sum_ {k = 1}^{n - 1} \sum_ {r = 0}^{k - 1} \binom { \frac {n - r}{k}}{2} \le f(n) < 1 + n + \sum_ {k = 1}^{n - 1} \sum_ {r = 0}^{k - 1} \binom { \frac {n - r}{k} + 1}{2} \\ \sum_ {k = 1}^{n - 1} \sum_ {r = 0}^{k - 1} \frac12\cdot\frac {n - r}{k} \left ( \frac {n - r}{k} - 1 \right ) \le f(n) - 1 - n < \sum_ {k = 1}^{n - 1} \sum_ {r = 0}^{k - 1} \frac12\cdot\frac {n - r}{k} \left ( \frac {n - r}{k} + 1 \right ) \\ \sum_ {k = 1}^{n - 1} \sum_ {r = 0}^{k - 1} \frac {1}{k^2}(n - r - k)(n - r) \le 2(f(n) - 1 - n) < \sum_ {k = 1}^{n - 1} \sum_ {r = 0}^{k - 1} \frac {1}{k^2}(n - r)(n - r + k) \\ \sum_ {k = 1}^{n - 1} \frac {1}{k^2} \sum_ {r = 0}^{k - 1}(n^2 + O(kn)) \le 2(f(n) - 1 - n) < \sum_ {k = 1}^{n - 1} \frac {1}{k^2} \sum_ {r = 0}^{k - 1}(n^2 + O(kn)) \\ \sum_ {k = 1}^{n - 1} \frac {1}{k^2}(kn^2 + O(k^2n)) \le 2(f(n) - 1 - n) < \sum_ {k = 1}^{n - 1} \frac {1}{k^2}(kn^2 + O(k^2n)) \\ n^2 \sum_ {k = 1}^{n - 1} \left ( \frac {1}{k} + O \left ( \frac1n\right ) \right ) \le 2(f(n) - 1 - n) < n^2 \sum_ {k = 1}^{n - 1} \left ( \frac {1}{k} + O \left ( \frac1n\right ) \right ) \\ n^2 \ln n \sim n^2(H_{n - 1} + O(1)) \le 2(f(n) - 1 - n) < n^2(H_{n - 1} + O(1)) \sim n^2 \ln n.$$ Así, $f(n) \sim \frac12n ^2 \ln n$ .

Answer 2

\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)$$