La forma cerrada de la expresión para el recuento de las "carreras" en secuencia binaria compartir la misma longitud, el número de 1's, y la ubicación de final 1

Question

Estoy luchando con el siguiente problema combinatorio relacionadas con la investigación que estoy haciendo.

Tomar una secuencia binaria $(y_1, y_2, \ldots, y_n)$ de la longitud de la $n$ con $x$ $1$'s, donde el final de la $1$ es en la ubicación de $t_x$ (en inglés: $t_x$ es el tiempo de la $x$th evento). Deje que el número de carreras de duración $2$ (lo que permite la superposición - ver ejemplos a continuación para hacer esto más fácil de entender) se denota por a $n_{runs}$. Para ser más precisos, $n_{runs}$ es el número de veces que tenemos que $y_{k-1} = y_k = 1, k \in \{1, 2, \ldots, n \}$ (informalmente, "el número de veces que vemos a $11$ en nuestra secuencia"). Para lidiar con los problemas de inicio de al $k=1$, suponemos que $y_1=1$ contribuye de una carrera a $n_{runs}$.

Un par de ejemplos para hacer este concreto:

(1) $(y_1, y_2, y_3) = 110$: Aquí, $x=2, t_x=2, n_{runs}=2, n=3$ (de nuevo en la observación de la inicialización de la asunción de $y_1$).

(2) $(y_1, y_2, \ldots, y_8) = 11001010$: Aquí, $x=4, t_x = 7, n_{runs}=2, n=8$.

(3) $(y_1, y_2, \ldots, y_5 ) = 01110$: Aquí, $x=3, t_x = 4, n_{runs}=2, n=5$.

(4) $(y_1, y_2, \ldots, y_5 ) = 01100$: Aquí, $x=2, t_x = 3, n_{runs}=1, n=5$.

Me gustaría saber la siguiente fijación de $n$, ¿cuántas secuencias comparten la misma combinación de $(x, t_x, n_{runs}, n)$? Hay una forma cerrada de expresión para esto? Por supuesto, la aproximación de fuerza bruta es simplemente enumerar todas las secuencias que comparten el mismo $(x,t_x,n)$ estadísticas, luego de contar las pistas, pero sería agradable si había alguna manera de conseguir esto en forma cerrada.

Podemos ver que el número de secuencias que comparten el mismo $(x,t_x,n)$ ${ t_x-1 \choose x-1 }$ para todos los casos dentro del soporte ($x \in \{ 0, \ldots, n \}, t_x \in \{ x, \ldots, n \}$) a excepción de $x=0, t_x=0$, por lo que donde hay sólo 1 secuencia.

Algunas de las cosas que sabemos, para ayudar a ganar la intuición para el problema:

(1) Marginalmente, sabemos $n_{runs}$ puede ser mayor que $x$.

(2) Cuando $x=t_x=0$, sólo hay 1 secuencia con el mismo $(x,t_x,n_{runs},n)$. Es $(0,0,0,n)$.

(3) Cuando $x=1$, luego $t_x \in \{1, 2, \ldots, n \}$. $n_{runs} = 1$ al $t_x=1$ $0$ lo contrario (todas las combinaciones son únicos)

(4) Cuando $x \geq 2$, entonces si $t_x = x$, $n_{runs}=x$ y todas las combinaciones son únicos.

(5) Si $x=2$, entonces si $t_x \geq 3$, $n_{runs}=1$ se produce 2 veces, mientras que $n_{runs}=0$ se produce ${t_x - 1 \choose x-1} -2$ veces.

(6) se puede demostrar que existe una relación de recurrencia de identidad para los mayores valores de $x$,cuando sucesivamente condición en la que el primer elemento se $1$ o $0$, luego el segundo, y así sucesivamente y así sucesivamente. Esto debería conducir a algo más limpio que el enumerativa de aproximación de fuerza bruta, pero no demasiado bonita.

Muchas gracias a todos.

Answer 1

Las pistas son contados como si siempre hay un $1$ en la posición $0$$x+1$. En bloque, que sería considerado como $x$ pistas. Para reducir a $n_{runs}$ se ejecuta, este bloque tiene que ser dividido exactamente $k=x - n_{runs}$ lugares, $k\ge 0$, produciendo $k+1$ dichos bloques.

Considerar, entonces, contar el número de secuencias binarias $y_0, y_1, \ldots, y_t$ que consisten en la alternancia de bloques de unos y ceros, ambos comenzando y terminando con bloques de unos y habiendo $k+1$ bloques de (y, por tanto, $k$ bloques de ceros). El número total de ceros es $t-x = y$. Estas secuencias se encuentran en una correspondencia uno a uno con los pares ordenados $(c, d)$ donde $c$ es una composición de $x+1$ dando los recuentos de las $k+1$ uno de los bloques (en orden) y $d$ es una composición de $y$ dando los recuentos de las $k$ cero bloques (en este orden).

Debido a que la composición de la $a$ cosas en $b$ partes está determinada por la identificación de las $b-1$ espacios entre los $a$ cosas donde las roturas que se producen, el número de estas composiciones es el número de $(b-1)$-subconjuntos de la $a-1$ espacios, igual a $\binom{a-1}{b-1}$. En consecuencia, para $n\ge t$, la respuesta es

$$\binom{x}{k}\binom{y-1}{k-1}$$

con $k=x - n_{runs}$$y = t-x$. (Observe que $n$ no juega ningún papel: sólo se determina el número de ceros a su lugar después de $y_t$.) Para $n\lt t$, la respuesta es cero.

---

Considere, por ejemplo, las configuraciones $(x, t, n_{runs}, n) = (5, 9, 2, n)$, por lo que $k=5-2=3$$y=9-5=4$. La fórmula da $\binom{5}{3}\binom{3}{2}=30$ posibilidades, construido a partir de la $4$-composiciones de $6$ y el $3$-composiciones de $4$ ceros. Los primeros son

$$6 = 1+1+1+3 = 1+1+2+2 = 1+1+3+1 = 1+2+1+2 = 1+2+2+1\\ = 1+3+1+1 = 2+1+1+2 = 2+1+2+1 = 2+2+1+1 = 3+1+1+1$$

mientras que el segundo se

$$4 = 1+1+2 = 1+2+1 = 2+1+1.$$

Para ilustrar la correspondencia entre secuencias binarias y de pares ordenados de composiciones, considere la primera composición de cada grupo. La composición de la $6=1+1+1+3$ designa a los bloques de $1,1,1, 111$ de aquellos, mientras que la composición de la $4=1+1+2$ designa a los bloques de $0,0,00$ de los ceros a poner entre ellos, dando lugar a la correspondiente secuencia de

$$(1+1+1+3, 1+1+2)\to 1\ 0\ 1\ 0\ 1\ 00\ 111$$

Esto es seguido por $n-t$ ceros y la inicial (para $y_0$) deberían ser descartados. Efectivamente, la secuencia resultante, $0101001110\ldots 0$ $x=5, t=9, n_{runs}=2$ como estaba previsto.

Yendo en la otra dirección, considere la secuencia de $00\ 1\ 000\ 1111\ 0\ 1\ 0000$, por lo que $(x,t,n_{runs},n)=(6, 12, 3, 16).$ Ignorando el final de la $n-t=4$ ceros, que tiene que estar allí, y el prefijo de la secuencia con $y_0=1$ rendimientos $(y_0, y_1, \ldots, y_t) = 1\ 00\ 1\ 000\ 1111\ 0\ 1$. Esto muestra una de cuatro composición $1+1+4+1$ de los siete uno y tres-composición $2+3+1$ de seis ceros, de ahí la correspondencia es

$$1\ 00\ 1\ 000\ 1111\ 0\ 1 \to (1+1+4+1, 2+3+1).$$