Loading [MathJax]/jax/element/mml/optable/Latin1Supplement.js

6 votos

Contar el número de secuencias coincidentes exactas

Considere todos los pares de cuerdas binarias P y T . Que la longitud de P ser n y la longitud de T ser 2n1 . 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,,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?

5voto

Smylic Puntos 647

Lemma. Deje que R=R(P,T) ser una secuencia de salida para determinadas cadenas P y T de longitud n y 2n1 en consecuencia. Luego R=000non-negative number of zeros100k1 zeros100k1 zeros1100k1 zeros1non-negative number of ones000non-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=whatever1000k1 zeros10001 zeros1whatever para algunos números enteros positivos k . Deje que k< de lo contrario, podemos revertir todo P , T y R .

Deje que P=a0a1an1 donde ai son símbolos. Deje que $d = \gcd\ {\,k, \ell\ ,\}.LuegoT=T1P0P1PmT2,dondeT_iyP_isoncuerdastalesqueP = P_0 P_1 \ldots P_{x - 1}P'_x,|P_0| = |P_1| = \ldots = |P_{m - 1}| = d,0 \le |P_m| < dyP'_x = P_mesunprefijodeP_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 .

2voto

Tom G Puntos 11

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X