¿Cuál es el número de cadenas binarias de longitud N con exactamente R corre de unos, con total de C los?

Question

Estoy preocupado por el número total de, y el número total de carreras, pero no con el tamaño de cualquiera de las pistas.

Por ejemplo, $N=8$, $R=3$, $C=5$ incluye 11101010, 01101011 entre el 24 total de cadenas posibles.

Puedo calcular estos para las pequeñas $N$ bastante fácilmente, pero estoy especialmente interesado en la distribución de $N=65536$. Como esto va a resultar en grandes enteros, el registro de distribución de probabilidad es igual de útil.

He encontrado [1] y [2], que incluye esto:

Deje $N_{n;g_k,s_k}$ denotar el número de cadenas binarias que contienen por $g_k$ y $s_k$, $g_k=0,1,…,⌊\frac{s_k}{k}⌋$, $s_k=0,k,k+1,…,n$, exactamente $g_k$ carreras de 1 s de duración, al menos,$k$, con un total de 1 (con la suma de las longitudes de los recorridos de 1) exactamente igual a $s_k$ en todas las posibles cadenas binarias de longitud $n$.

Una expresión de esto es dado en la ecuación. (24):

$N_{n;g_k,s_k} = \sum_{y=0}^{n-s_k} {y+1 \elegir g_k } {s_k-(k-1)g_k-1 \elegir g_k-1} \sum_{j=0}^{⌊\frac{n-y-s_k}{k}⌋} (-1)^j {y+1-g_k \elegir j} {n-s_k-kj-g_k \elegir n-s_k-kj-y} $

for $g_k \in \{1, ..., ⌊\frac{s_k}{k}⌋\}$, $s_k \in \{k, k+1, ..., n\}$.

I think this is exactly what I'm looking for, with $k = 1$, $s_k = C$ and $g_k = R$. However, when I implemented this I did not get the expected results (Python shown below, edge cases omitted), based on comparing to counting all strings for N=8. I am working backwards to try to understand where I might have gone wrong, but not having much luck yet. I wonder if I am misunderstanding the result.

def F(x, y, n):
    # x = C or s_k (cardinality)
    # y = R or g_k (runCount)
    # n = N (total bits)

    a1 = 0
    for z in range(n-x+1):
        b1 = choose(z+1, y) * choose(x-1, y-1)
        a2 = 0
        for j in range(n-z-x+1):
            a2 += (-1) ** j * choose(z+1-y, j) * choose(n-x-j-y, n-x-j-z)
        a1 += b1 * a2

    return a1

Note that the choose function uses factorial, which I realize won't work for larger $N$ - but should be fine for $N=8$.

Edit: corregido un signo de error error tipográfico en la eq. (24) y el equivalente de error en el código de python.

[1] el Conteo se Ejecuta de unos y otras en las Carreras de en Cadenas binarias, Frosso S. Makri, Zaharias M. Psillakis, Nikolaos Kollas https://file.scirp.org/pdf/OJAppS_2013011110241057.pdf

[2] En caso de éxito se ejecuta de una longitud fija en la de Bernoulli secuencias: Exacto asintótica y resultados, Frosso S. Makria, Zaharias M. Psillakis http://www.sciencedirect.com/science/article/pii/S0898122110009284

Answer 1

Considere una cadena binaria y vamos a poner un adicional (dummy) fija $0$ al inicio de la misma. Nos individualizar como ejecutar un $0$, seguido por contiguos $1$'s.

Por tanto, dada una cadena de longitud $N$ total de $C$, y el número de pistas $R$, tendremos $N-C$ ceros, de los cuales, $N-C-R+1$ son "gratis", que no es firme, para marcar las pistas.

El número de formas para constituir las pistas es el número de (standard) composiciones de $C$ a $R$ partes, que es $$ {{C-1} \choose {R-1}}$$.
El número de maneras de colocar el "libre" ceros será igual al número de débil composiciones de su número en $R+1$ partes (en frente de la primera y, a continuación, después de cada ejecución), es decir: $$ {{N-C-R+1+R+1-1} \choose {R}}={{N-C+1} \choose {R}}$$.

Lo que confirma N. Lutitas's respuesta, por lo que el mérito que deben ir a él.

Anexo

Respecto de la fórmula (24), por lo que puedo ver, parece que en la 3ª binomio ${{y+1+g_k} \choose {j}}$ no es una señal de error tipográfico, y que debería ser $\cdots -g_k$.
A continuación, poner por ejemplo $k=1,\; s_k=n-1 \; g_k=2$ va correctamente dará $n-2$,
y con $k=1,\; s_k=C \; g_k=R$ va a dar la fórmula de arriba.
Pero al no tener el texto completo, no puedo comprobar que más.

Answer 2

Quizás hay algo de valor en la solución de este con funciones de generación. En el presente caso, tenemos marcada la generación de la función con $z$ para unos y $w$ de los ceros y los $y$ carreras de la

$$(1+y(z+z^2+z^3+\cdots)) \\ \times \left(\sum_{q\ge 0} (w+w^2+w^3+\cdots)^q y^q (z+z^2+z^3+\cdots)^q\ \ derecho) \\ \times (1+w+w^2+w^3+\cdots).$$

Este es

$$\left(1+\frac{yz}{1-z}\right) \times \left(\sum_{q\ge 0} \frac{w^p}{(1-w)^p} y^q \frac{z^p}{(1-z)^p}\right) \times \frac{1}{1-w} \\ = \left(1+\frac{yz}{1-z}\right) \times \frac{1}{1-ywz/(1-w)/(1-z)} \times \frac{1}{1-w}.$$

Extraer el coeficiente de $[y^R]$ $R$ ejecuta tenemos

$$\frac{w^R z^R}{(1-w)^R (1-z)^R} \frac{1}{1-w} + \frac{z}{1-z} \frac{w^{I-1} z^{I-1}}{(1-w)^{I-1} (1-z)^{I-1}} \frac{1}{1-w}.$$

A continuación hacer el coeficiente de $[z^C]$ $C$ queridos

$$[z^{C-R}] \frac{w^R}{(1-w)^R (1-z)^R} \frac{1}{1-w} + [z^{C-R}] \frac{w^{I-1}}{(1-w)^{I-1} (1-z)^{R}} \frac{1}{1-w} \\ = {C-1\elegir R-1} \frac{w^R}{(1-w)^{I+1}} + {C-1\elegir R-1} \frac{w^{I-1}}{(1-w)^{R}}.$$

Finalmente extraer $[w^{N-C}]$ para el resto de los ceros:

$${C-1\elegir R-1} [w^{N-C-R}] \frac{1}{(1-w)^{I+1}} + {C-1\elegir R-1} [w^{N-C-R+1}] \frac{1}{(1-w)^{R}} \\ = {C-1\elegir R-1} {N-C\elegir R} + {C-1\elegir R-1} {N-C\elegir R-1} \\ = {C-1\elegir R-1} {N-C+1\elegir R}.$$

Esto confirma la aceptación de la respuesta, sin crédito reclamado aquí.