Recuento de secuencias casi coincidentes

Question

Considere todos los pares de cadenas binarias $P$ y $T$ . Sea la longitud de $P$ sea $n$ y la longitud de $T$ sea $2n-1$ . Para cada uno de estos pares, podemos calcular la distancia de Hamming entre $P$ y cada uno de los $n$ subcadenas de $T$ en orden de izquierda a derecha y mostrar una secuencia que represente estos resultados. Por ejemplo:

$$P = 11011, T = 110011001$$

da una secuencia de salida:

$$1,1,4,4,1.$$

Para mi problema sólo quiero registrar dónde la distancia de Hamming es como máximo 1. Escribimos a $Y$ en este caso y un $N$ de lo contrario. Así que en este caso me pondría:

$$Y,Y,N,N,Y$$

donde $Y$ representa la distancia Hamming como máximo $1$ y $N$ representa una distancia Hamming superior a $1$

Si iteramos sobre todos los pares posibles $P$ , $T$ podemos contar cuántas secuencias distintas de $Y$ s y $N$ s que obtenemos de las salidas. Para $n = 1, \dots, 9$ obtenemos el siguiente resultado interesante:

$$1 ,4, 8, 16, 32, 63, 120, 216, 368$$

¿Es posible dar una fórmula cerrada para el número de secuencias distintas de $Y$ s y $N$ s?

Relacionado En Número de secuencias que coinciden exactamente Smylic da una solución muy buena que corresponde a este problema con un límite de distancia de Hamming de $0$ más bien $1$ .

Answer 1

Demostraré que el número $F_1(n)$ de secuencias casi coincidentes está en $\Omega(n^2 \log n)$ . Utilizaré mi resultado anterior que el número $F_0(n)$ de secuencias coincidentes exactas es $\frac12 n^2 \ln n (1 + O(1))$ . (La única diferencia en la definición de este tipo de secuencias es que Y corresponde a una distancia de Hamming nula que se refleja en el índice inferior).

1. $F_1(2n) \ge F_0(n)$ .
   Prueba. Sea $P = p_1p_2\ldots p_n$ y $T = t_1t_2\ldots t_{2n-1}$ producir una secuencia coincidente exacta $m_1m_2\ldots m_n$ . Entonces $P' = p_1p_1p_2p_2\ldots p_np_n$ y $T' = t_1t_1t_2t_2\ldots t_{2n-1}t_{2n-1}0$ producir una secuencia casi idéntica $m_1x_1m_2x_2\ldots m_nx_n$ para algunos $x_1, x_2, \ldots x_n$ . La razón es que la distancia $d$ entre $P$ y $t_i\ldots t_{i + n - 1}$ da exactamente la distancia $2d$ entre $P'$ y $t_it_i\ldots t_{i + n - 1}t_{i + n - 1}$ . $\square$

2. $F_1(2n+1) \ge F_0(n)$ .
   Prueba. Sea $P = p_1p_2\ldots p_n$ y $T = t_1t_2\ldots t_{2n-1}$ producir una secuencia casi idéntica $m_1m_2\ldots m_n$ . Entonces $P' = p_1p_1p_2p_2\ldots p_np_n0$ y $T' = t_1t_1t_2t_2\ldots t_{2n-1}t_{2n-1}000$ producir una secuencia casi idéntica $m_1x_1m_2x_2\ldots x_{n-1}m_nx_nx_{n+1}$ para algunos $x_1, x_2, \ldots x_{n+1}$ . La razón es que la distancia $d$ entre $P$ y $t_i\ldots t_{i + n - 1}$ da la distancia o bien $2d$ o $2d + 1$ entre $P'$ y $t_it_i\ldots t_{i + n - 1}t_{i + n - 1}t_{i + n}$ où $t_{2n} = 0$ . $\square$

Por lo tanto $F_1(n) \ge F_0(\lfloor n/2 \rfloor) \sim \frac{n^2}{8} \ln n$ y $F_1(n) = \Omega(n^2 \log n)$ . Este límite puede ser bastante débil.

---

Conjetura. Cada secuencia casi coincidente con al menos dos Y tiene la siguiente forma: $$N \times n_1, (Y, N \times n_2) \times n_3, Y, N \times (n_2n_4 + n_4 - 1), Y, (N \times n_2, Y) \times n_5, N \times n_6,$$ donde $S \times k$ significa secuencia $S$ repetido $k$ tiempos y $n_i$ son enteros no negativos. Además, cada una de estas secuencias es una secuencia casi coincidente.

Esto implicaría que $F_1(n) = \Theta(n^4)$ .

Fue fácil descubrir que esta conjetura es errónea comparando el número de secuencias descritas con el número de secuencias casi coincidentes. Incluso para $n = 6$ hay secuencias casi coincidentes YNNYNY , YNYNNY , YNYNYY y YYNYNY que tienen otro patrón. Sin embargo, puede ser posible utilizar el número de secuencias descritas como límite inferior para el número de secuencias casi coincidentes.

---

Resultados computacionales: $$\begin{array}{c|c|c|c} n & F_1(n) & \frac{F_1(n)}{n^4} & \frac{F_1(n)}{n^4 \ln n}\\\hline 1 & 1 & 2 & -\\ 2 & 4 & 0.25 & 0.361\\ 3 & 8 & 0.099 & 0.090\\ 4 & 16 & 0.063 & 0.045\\ 5 & 32 & 0.051 & 0.032\\ 6 & 63 & 0.049 & 0.027\\ 7 & 120 & 0.050 & 0.026\\ 8 & 216 & 0.054 & 0.025\\ 9 & 368 & 0.056 & 0.026\\ 10 & 596 & 0.060 & 0.026\\ 11 & 930 & 0.064 & 0.026\\ 12 & 1387 & 0.067 & 0.027\\ 13 & 2009 & 0.070 & 0.027\\ 14 & 2818 & 0.073 & 0.028\\ 15 & 3872 & 0.076 & 0.028\\ 16 & 5191 & 0.079 & 0.029\\ 17 & 6850 & 0.082 & 0.029\\ 18 & 8838 & 0.084 & 0.029\\ 19 & 11310 & 0.087 & 0.029\\ 20 & 14209 & 0.089 & 0.030\\ 21 & 17687 & 0.091 & 0.030\\ 22 & 21719 & 0.093 & 0.030\\ 23 & 26512 & 0.095 & 0.030\\ 24 & 31938 & 0.096 & 0.030\\ \end{array}$$

EDITAR. Viendo estos resultados supongo que $F_1(n)$ está cerca de $\frac1{30}n^4 \ln n$ .

Answer 2

(Publico una nueva respuesta porque da un límite mucho mejor y una caracterización casi completa de las secuencias casi coincidentes).

Conjetura. Cada secuencia casi coincidente $S$ cumple al menos una de las siguientes condiciones:

1. Hay un número $d$ tal que la distancia entre cada par de Y sucesivos es $d$ como máximo con una excepción de distancia que no es $d$ pero es divisible por $d$ .
2. Hay un número $d$ tal que la distancia entre cada par de Y sucesivos es $d$ con exactamente dos excepciones divisibles por $d$ y son dos distancias a la izquierda o dos distancias a la derecha.
3. Secuencia $S$ tiene exactamente cuatro Y y satisface algunas otras restricciones.

También cada secuencia que satisface al menos una de estas condiciones excepto N simple es una secuencia casi coincidente.

Ejemplos de secuencias casi coincidentes de cada tipo:

1. NYYYYYYYYNNYYYYYYYYYNNN , NNYYYYYYYYYYYYYYNNNNN , NNNNNNNNNNNNNNN , NYNYNYNYNYNYNNNYNYNNNNN .
2. NYYYYYNNYNNNNNNNNNNNNNN , YNNYNNYNNYNNNNNNNNNNNNN , YNNYNNYYYNNNNNNNNNNNN .
3. YNYNNNNNNNNNNNNNNN , NNNYNNNNYNNNNNNNNYNNNNY .

Esta conjetura se comprobó para todos los $n \le 22$ . Demostremos que todas las secuencias que cumplen la primera o la segunda condición son secuencias casi coincidentes.

Reclamación 1. Todas las secuencias que cumplen la primera condición son secuencias casi coincidentes.
Prueba. TODO $\square$

Reclamación 2. Todas las secuencias que cumplen la segunda condición son secuencias casi coincidentes.
Prueba. TODO $\square$

Para probar la conjetura se necesitan más detalles en la tercera condición. Sin embargo, podemos calcular el número de secuencias casi coincidentes que satisfacen la primera o la segunda condición.

Una secuencia sin Y está cerca de la secuencia coincidente si $n > 1$ , $n$ secuencias con una Y son secuencias casi coincidentes. Calculemos ahora todas las demás secuencias casi coincidentes que cumplan la primera condición. Podemos elegir cualquier $d$ entre $1$ y $n - 1$ inclusive. Además elegimos el residuo del extremo izquierdo Y posición modulo $d$ (cualquier $r$ entre $0$ y $d - 1$ inclusive). Entonces, para el caso de todas las distancias iguales a $d$ elegimos sólo las posiciones más a la izquierda y más a la derecha de Y en $\left\lceil\frac{n - r}{d}\right\rceil$ posibles en $\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2}$ maneras. Si tenemos una distancia distinta de $d$ es lo mismo que elijamos dos bordes más para que falten Y 's. Aquí necesitamos tener al menos tres Y 's. Y hay algunos casos: más a la izquierda Y es único (es decir, tiene una distancia superior a $d$ a la siguiente), derecha Y es único, ni a la izquierda ni a la derecha Y es soltero. Dos primeros casos dan $\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3}$ maneras cada uno y el último da $\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4}$ maneras. (Menos uno significa aquí que, en primer lugar, disminuimos el número de posiciones posibles para el motivo a insertar N entre las partes izquierda y derecha de Y 's.) Así pues, tenemos $$[n > 1] + n + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2} + 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3} + \binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4}$$ en total para el número de secuencias casi coincidentes que satisfacen la primera condición.

Para la segunda condición tenemos la misma situación con $d$ y $r$ . Además hay dos casos: hay al menos cuatro Y 's en $2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4}}$ formas (donde $\overline{\binom{n}{k}}$ significa $\binom{\max\{\,0, n\,\}}{k}\,\}$ ) para elegir el lado izquierdo o derecho, las posiciones de la única Y y la gama de otros Y (menos dos significa que disminuimos el número de posiciones posibles para insertar después dos n ), o hay exactamente tres Y 's. Para calcular el número de vías en el último caso es mejor eliminar las triplas contadas anteriormente de Y dando distancias iguales y triples de Y y triples de Y en dos distancias no iguales pero divisibles por un lado y luego sumar todos los triples de Y 's: $$\binom{n}{3} + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1} 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4} - \binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{1} - 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{2}.$$

Sólo para mostrar cuántas secuencias casi coincidentes se cuentan y cuántas no, doy la siguiente tabla: $$\begin{array}{c|c|c|c} n & F_1(n) & \text{The first condition} & \text{The second condition}&\text{Remaning}\\\hline 1 & 1 & 1 & 0 & 0 \\ 2 & 4 & 4 & 0 & 0 \\ 3 & 8 & 8 & 0 & 0 \\ 4 & 16 & 16 & 0 & 0 \\ 5 & 32 & 32 & 0 & 0 \\ 6 & 63 & 59 & 4 & 0 \\ 7 & 120 & 106 & 14 & 0 \\ 8 & 216 & 175 & 40 & 1 \\ 9 & 368 & 280 & 88 & 0 \\ 10 & 596 & 425 & 170 & 1 \\ 11 & 930 & 627 & 300 & 3 \\ 12 & 1387 & 885 & 494 & 8 \\ 13 & 2009 & 1235 & 768 & 6 \\ 14 & 2818 & 1664 & 1142 & 12 \\ 15 & 3872 & 2207 & 1646 & 19 \\ 16 & 5191 & 2869 & 2292 & 30 \\ 17 & 6850 & 3687 & 3122 & 41 \\ 18 & 8838 & 4642 & 4148 & 48 \\ 19 & 11310 & 5806 & 5428 & 76 \\ 20 & 14209 & 7142 & 6964 & 103 \\ 21 & 17687 & 8731 & 8826 & 130 \\ 22 & 21719 & 10555 & 11020 & 144 \\ 23 & 26512 & 12667 & 13628 & 217 \\ 24 & 31938 & 15033 & 16636 & 269 \\ \end{array} $$

Es fácil ver que la incierta tercera condición no da muchas nuevas secuencias casi coincidentes. Más interesante es que esta secuencia no es decreciente.

Para calcular la asíntota del número de secuencias casi coincidentes podemos observar que hay como máximo $\binom{n}{4}$ secuencias que satisfacen la tercera condición si la conjetura es cierta. Por lo tanto, si la conjetura es cierta, entonces hay $F_1(n)$ secuencias coincidentes cercanas tales que $$g(n) \le F_1(n) \le g(n) + \binom{n}{4}$$ donde $$g(n) = [n > 1] + n + \binom{n}{3} + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2} + 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3} + \binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4} + \\ 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4}} - \overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{1}} - 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{2}}\\ =o(n^4) + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2} + 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3} + \binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4} + \\ 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4}} - \overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{1}} - 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{2}}.$$

Busquemos la asíntota de $\sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - a}{b}}$ para números enteros constantes $a$ y $b$ ( $a \ge 0$ , $1 \le b \le 4$ ). $$h(n, a, b) = \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - a}{b}}\\ = \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}[n - r > (a + b - 1)d]\binom{\left\lceil\frac{n - r}{d}\right\rceil - a}{b}\\ = \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\left\lceil\frac{n - r}{d}\right\rceil - a}{b}.$$

Por lo tanto $$\sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} - a}{b} \le h(n, a, b) < \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} + 1 - a}{b},\\ \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} - a}{b} \le h(n, a, b) < \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} + 1 - a}{b}.$$

Para $b \le 3$ : $$h(n, a, b) < \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} + 1 - a}{b} \le \sum_{d = 1}^{n - 1}d\binom{\frac{n}{d} + 1 - a}{b} \le\\ \sum_{d = 1}^{n - 1}d\binom{\frac{n}{d} + 1 - a}{b} = \sum_{d = 1}^{n - 1} O\left(d\frac{n^b}{d^b}\right) = \sum_{d = 1}^{n - 1} O(n^b d^{1 - b}) = o(n^4).$$

Y para $b = 4$ encontramos límites superiores e inferiores. Empecemos por el inferior. $$h(n, a, 4) \ge \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 4 - 1)d - 1\,\}}\binom{\frac{n - r}{d} - a}{4} >\\ \sum_{d = 1}^{\left\lfloor\frac{n - 1}{a + 3}\right\rfloor}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 3)d - 1\,\}}\binom{\frac{n}{d} - 1 - a}{4} = \\ \sum_{d = 1}^{\left\lfloor\frac{n - 1}{a + 3}\right\rfloor}\sum_{r = 0}^{d - 1}\frac{1}{24}\left(n^4d^{-4} + O(n^3 d^{-3}) + O(n^2 d^{-2}) + O(n d^{-1}) + O(1)\right) = \\ \sum_{d = 1}^{\left\lfloor\frac{n - 1}{a + 3}\right\rfloor}\frac{1}{24}\left(n^4d^{-3} + O(n^3 d^{-2}) + O(n^2 d^{-1}) + O(n) + O(d)\right) \sim \\ \frac{\zeta(3)}{24}n^4 \approx 0.05n^4, $$ donde $\zeta(\cdot)$ es la función zeta de Riemann. Y continuamos con el límite superior. $$h(n, a, 4) < \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 4 - 1)d - 1\,\}}\binom{\frac{n - r}{d} + 1 - a}{4} \le\\ \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 3)d - 1\,\}}\binom{\frac{n}{d} + 1 - a}{4} = \\ \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 3)d - 1\,\}}\frac{1}{24}\left(n^4d^{-4} + O(n^3 d^{-3} + O(n^2 d^{-2} + O(n d^{-1}) + O(1)\right) \le\\ \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\frac{1}{24}\left(n^4d^{-4} + \max\{\,0, O(n^3 d^{-3} + O(n^2 d^{-2} + O(n d^{-1}) + O(1)\,\}\right) \sim\\ \frac{\zeta(3)}{24}n^4 \approx 0.05n^4\\ $$

Por lo tanto $$h(n, a, 4) \sim \frac{\zeta(3)}{24}n^4 \approx 0.05n^4.$$

Ahora observamos que $\binom{n}{k} = \overline{\binom{n}{k}}$ si $n \ge k$ y volver a $g(n)$ . $$g(n) = o(n^4) + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2} + 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3} + \binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4} + \\ 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4}} - \overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{1}} - 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{2}} \sim\\ \frac{3\zeta(3)}{24}n^4 = \frac{\zeta(3)}{8}n^4 \approx 0.15 n^4. $$

Desde $$g(n) \le F_1(n) \le g(n) + \binom{n}{4}$$ concluimos que $$F_1(n) = \Theta(n^4).$$

Esta estimación no coincide con la tabla calculada anteriormente, pero 24 no es un número tan grande.