Número de posibles secuencias de bits de longitud m con al menos n 1 consecutivos en ellas
He visto preguntas similares a esta, pero cada una parece ser un caso especial de esta pregunta general. Responder esto sería beneficioso para mi investigación, pero no soy un experto en combinatoria, y esta pregunta aparentemente simple se me escapa. ¿Existe una fórmula sencilla para calcular esto? Todo lo que he visto en línea se ha centrado en cosas como "2 1 o 0 consecutivos" o "no contiene ...".
Si ayuda, lo sé por $m = 8$ bits y dicen que la secuencia se denota $S(m,n)$ $$ S(m = 8, n = 1) = 255 \\ S(8,2) = 201 \\ S(8,3) = 107 \\ S(8,4) = 48 \\ S(8,5) = 20 \\ S(8,6) = 8 \\ S(8,7) = 3 \\ S(8,8) = 1 $$
Curiosamente estoy encontrando que $S(8,4)=S(9,5)=S(10,6)=S(11,7)=48$ No he probado $S(12,8)$ porque no quiero que mi computadora se derrita pero veo un patrón ... Sin embargo, esto no parece funcionar para $m<8$.
Respuestas
Gracias a la fórmula de @Ross Millikan, que busqué con Approach Zero , pude encontrar esta respuesta , y usando de nuevo Approach Zero con ese resultado, esta otra hermosa respuesta . Ambos dan el resultado complementario, así que en tu caso tenemos:
$$S(m,n) = 2^m-\sum_{q=0}^{\lfloor m/n\rfloor} {m-nq\choose q} (-1)^q 2^{m-(n+1)q} + \sum_{q=0}^{\lfloor m/n\rfloor - 1} {m-n(q+1)\choose q} (-1)^q 2^{m-n-(n+1)q}$$
Consulte los enlaces para obtener más detalles.
Si la cadena es $m$ bits de largo y exige una serie de exactamente $n\ 1$s podemos encontrar una fórmula para $n \ge \frac m2$. Llamemos a esto$T(m,n)$. Si la carrera está en un extremo de la cadena ($2$ opciones) necesitas un $0$ al final de la carrera y tener $2^{m-n-1}$opciones para los otros bits. Si la carrera no está al final de la cadena, hay$m-n-1$ lugares en los que puede empezar y tienes $2^{m-n-2}$opciones para completar la cadena. Si$m-n-2$ es negativo, no hay otros bits para completar. $$T(m,n)=\begin {cases} 1&n=m\\2&n+1=m\\2^{m-n}+(m-n-1)2^{m-n-2}&n+2 \le m \end {cases} $$ y el hecho de que solo depende de $m-n$es claro. Luego$$S(m,n)=\sum_{i=n}^mT(m,i)$$ Repito que esto solo funciona para $n \ge \frac m2$. La razón por la que solo depende de$m-n$ es porque si tomas una cadena del tipo $(m,n)$ puedes encontrar una cadena única de tipo $(m+1,n+1)$ extendiendo la carrera un poco más.
No daré una fórmula, solo una relación de recurrencia. Sea T (m, n) el número de cadenas de longitud m con una serie de n unos consecutivos.
Considere todas las cuerdas de longitud m-1. Exactamente T (m-1, n) de ellos ya contienen una cadena de 'n' dígitos consecutivos. Como podemos agregar un 0 o un 1, obtendremos el doble de esta cantidad de cadenas de longitud m cadenas.
Sin embargo, agregar un 1 en el mésimo lugar dará una nueva cadena buena si los últimos (n-1) dígitos son un 1 y el n ° al último dígito es un 0 y además los dígitos en el lugar 1, .. ., m - n - 1 no contienen una serie de n unos consecutivos. es decir, la cadena se ve así:$$ \underbrace{xx..xx}_{m - n - 1}0\underbrace{11..11}_{n - 1} $$ Hay 2 ^ {m - n - 1} posibilidades para los dígitos x, pero deberíamos excluir T (m - n - 1, n) de ellos para evitar el doble conteo.
Sumando todo encontramos $$ T(m, n) = 2\cdot T(m - 1, n) - T(m - n - 1, n) + 2^{(m - n - 1)} $$
Si $m - n - 1 \leq n$, es decir $m \leq 2n + 1$, la $T(m - n - 1, n)$ el término desaparece y debería poder resolver la relación de recurrencia.