Número de cadenas binarias únicas que contienen al menos m 1s secuenciales

Question

Dejemos que $Z\left(n,m\right)$ sea el número de cadenas binarias únicas de longitud $m$ que contiene al menos una instancia de $n$ consecutivos de 1. Estoy tratando de encontrar una expresión para $Z$ preferiblemente calculable directamente, aunque también acepto una solución recursiva. He intentado una formulación basada en [1] , $$ \hat{Z}\left(n,m\right) = \sum_{q=m}^{n}\sum_{i=1}^{\lfloor \frac{q}{m}\rfloor}(-1)^{i+1}\binom{n-q+1}{i}\binom{n-mi}{n-q}\text{,}$$ Sin embargo, estoy obteniendo algunas discrepancias con los casos de prueba que elaboré a mano. Por ejemplo, funciona para $Z\left(7,6\right)=3$ y $Z\left(7,5\right)=8$ pero no funciona para $\left(7,4\right)=16$ (la formulación anterior da $20$ ). N.B. : mis definiciones de $n$ y $m$ son opuestas a las de [1]; $q$ es el mismo.

Creo que tiene algo que ver con el doble conteo de algunas permutaciones de cadenas, pero no he podido averiguar qué más tengo que quitar.

Actualización : He encontrado una formulación recursiva [2] que me da el mismo resultado que mi $\hat{Z}$ arriba: $$ \tilde{Z}\left(n,m\right) = 2\tilde{Z}\left(n-1,m\right) + 2^{n-m-1}-\tilde{Z}\left(n-m-1,m\right) $$ Al haber encontrado esta formulación independiente, tendré que revisar mi recuento y ver si me he equivocado en alguna parte.

Puntos extra por una respuesta que funcione para diccionarios arbitrarios, es decir $W\left(a,n,m\right)$ donde $a$ es el número de símbolos posibles en cada posición de la cadena. La pregunta original equivaldría a $Z\left(n,m\right) = W\left(2,n,m\right)$ .

• [1] G.L., Número de cadenas binarias que contienen al menos n 1 consecutivos
• [2] Gerry Myerson, respuesta a Número de cadenas de bits con 3 ceros consecutivos o 4 1s consecutivos

Answer 1

Puedes utilizar la combinatoria simbólica para obtener una función generadora. Es más fácil obtener el número de cadenas que no tienen $m$ consecutivos, y restar del total.

Llame a $\mathcal{B}_{1^m}$ el conjunto que busca, y $\mathcal{P}_{< m}$ el conjunto de cadenas de menos de $m$ de los mismos, es decir, $\{ \epsilon, 1, 11, \dotsc, 1^{m - 1} \}$ . Tenemos las siguientes ecuaciones simbólicas:

$\begin{align} \mathcal{P}_{< m} &= \mathcal{E} + \{ 1 \} + \dotsb + \{ 1 \}^{m - 1} \\ \mathcal{B}_{1^m} &= \mathcal{P}_{< m} + \mathcal{P}_{< m} \times \{ 0 \} \times \mathcal{B}_{1^m} \end{align}$

Esencialmente, una de sus cadenas es una cadena de menos de $m$ o una cadena de menos de $m$ unos, un cero y una cadena de la forma que buscamos.

Utilice $z$ para marcar la longitud, de modo que el símbolo en sí mismo es irrelevante, y escribir las ecuaciones para las funciones generadoras:

$\begin{align} P_{< m}(z) &= 1 + z + \dotsb + z^{m - 1} \\ &= \frac{1 - z^m}{1 - z} \\ B_{1^m}(z) &= P_{< m}(z) + P_{< m} \cdot z \cdot B_{1^m}(z) \\ &= \frac{1 - z^m}{1 - z} (1 + z B_{1^m}(z)) \end{align}$

Resolver:

$$ B_{1^m}(z) = \frac{1 - z^m}{1 - 2 z + z^{m + 1}} $$

Lo que se busca es el coeficiente de $z^n$ en esto. No hay una expresión sencilla para eso en el caso general. Para $m = 1$ lo es:

$$ B_1(z) = \frac{1 - z}{1 - 2 z + z^2} = \frac{1}{1 - z} $$

para que $Z(n, 1) = 2^1 - 1 = 1$ . No es ninguna sorpresa.

Si $m = 2$ que tienes:

$$ B_{11}(z) = \frac{1 - z^2}{1 - 2 z + z^3} = \frac{1 + z}{1 - z - z^2} $$

así que $Z(n, 2) = 2^n - F_{n + 2}$ , donde $F_n$ es un número de Fibonacci, definido por:

$$ F_0 = 0, F_1 = 1, F_{n + 2} = F_{n + 1} + F_n $$

Los casos $m = 3$ y $4$ son todavía factibles, pero son un horrible lío de raíces cuando se expande la función generadora en fracciones parciales.

Answer 2

Lo más fácil es contar las cadenas que no contienen las carreras de unos. Supongamos que se comienza con una cadena de $m$ los: $$1111111111\ldots1111111111\ \_$$ Para asegurarnos de que no hay cuatro unos consecutivos, sustituiremos los unos por ceros, saltando de izquierda a derecha, y aterrizando en el guión bajo.

Contar secuencias binarias sin de una longitud determinada equivale a la problema de las escaleras con cada pisada marcando el cero que impide una carrera.

Comience por considerar las secuencias sin 1111. Esto es como subir una escalera de altura $m$ con pasos de longitud 1, 2, 3 o 4. Sea $f(n)$ sea el número de formas de llegar al paso n. Si estás en el paso n, podrías haber llegado allí desde los pasos $n-1, n-2, n-3,$ o $n-4$ . Así, $$f(n) = f(n-1)+f(n-2)+f(n-3)+f(n-4)$$ y se comienza con $1, 2, 4, 8$ : $$1, 2, 4, 8, 15, 29, 56, 108$$

Tienes que llegar al paso 5 al menos, así que añade $15+29+56+108=208$ . Por lo tanto, hay $256-208=48$ secuencias que contienen 1111.

En cuanto a la situación con $a>2$ La única modificación es que cada pisada puede representar cualquiera de los $a-1$ dígitos que no son $1$ . Así, para la base $a$ cadenas, usaríamos $$f(n)=(a-1)(f(n-1)+f(n-2)+f(n-3)+f(n-4))$$ en su lugar.