¿Cuántas secuencias binarias de longitud n hay que contengan exactamente m ocurrencias del patrón 01?

Question

Pensé que había n-1 lugares entre el primer y el último dígito.
En estos lugares he hipotetizado que hay interruptores que cambian (de 0->1 o 1->0)

Para {First,Last}={00,01,10,11} -> 4 maneras

Pido una respuesta para el primer caso principalmente (creo que el resto será similar)

Dado que hay m patrones de 01, ¿cuántos interruptores hay?
¿Y cuántas formas hay de elegir entre n-1?

Answer 1

Método I

$\require{enclose} \newcommand{\bitP}[1]{\enclose{box}{#1}} $ Considere la siguiente codificación de $n$ -cadenas binarias de bits $$\bitP{a_0 a_1 a_2 \ldots a_{n-1}} \mapsto \bitP{b_0 b_1 b_2\ldots b_{n-1}}$$ definido por $$b_k = \begin{cases} a_k, &k = 0\\ a_k \oplus a_{k-1}, & 1 \le k \le n-1\end{cases}$$

donde $\oplus$ significa exclusiva lógica o entre dos bits.

Para que $\bitP{a_0 a_1 a_2 \ldots a_{n-1}}$ para tener exactamente $m$ copias de $\bitP{01}$ , hay cuatro posibilidades.
Dejemos que $N_m$ sean los números de $\bitP{1}$ entre los $n-1$ -Cadena binaria de bits $\bitP{b_1b_2\ldots b_{n-1}}$ Las cuatro posibilidades se pueden resumir en la siguiente tabla.

$$\begin{array}{cl:l} b_0 & N_m & \text{e.g.} (n=6, m=2) \\ \hline 0 & 2m - 1 & \bitP{010111} \mapsto \bitP{011100}\\ 0 & 2m & \bitP{010100} \mapsto \bitP{011110}\\ 1 & 2m & \bitP{101011} \mapsto \bitP{111110}\\ 1 & 2m + 1 & \bitP{101010} \mapsto \bitP{111111}\\ \end{array}$$

En base a esto, encontramos el número de $n$ -cadenas binarias de bits con exactamente $m$ copias de $\bitP{01}$ es dado por $$ \binom{n-1}{2m-1} + \binom{n-1}{2m} + \binom{n-1}{2m} + \binom{n-1}{2m+1}\\ = \binom{n}{2m} + \binom{n}{2m+1} = \binom{n+1}{2m+1} $$

Método II - función generadora.

En lugar de mirar la colección de $n$ -cadenas binarias de bits y preguntar cuántas de ellas tiene exactamente $m$ copias de $\bitP{01}$ . Observamos la colección de cadenas binarias con exactamente $m$ copias de $\bitP{01}$ y preguntar cuántos de ellos tiene la longitud $n$ .

La colección de cadenas binarias con exactamente $m$ copias de $\bitP{01}$ puede describirse mediante la siguiente expresión regular

$$1\verb/*/\;(\;0\verb/+/\;1\verb/+/\;)\{m\}\;0\verb/*/\tag{*1}$$

donde

• $X\verb/*/\;$ significa que el patrón $X$ se repite de cero a cualquier número de veces.
• $X\verb/+/\;$ significa que el patrón $X$ se repite de una a cualquier cantidad de veces.
• $X\{m\}\;$ significa que el patrón $X$ se repite exactamente $m$ tiempos.

Para contar el número de cadenas de bits con longitud $n$ asignamos a cada pieza en la expresión regular $(*1)$ por una serie de potencias en alguna indeterminada $t$ .

$$\begin{array}{ccl} 1\verb/*/\; & \leftrightarrow & \frac{1}{1-t} = 1 + t + t^2 + \ldots\\ 0\verb/+/\; & \leftrightarrow & \frac{t}{1-t} = t + t^2 + \ldots\\ 1\verb/+/\; & \leftrightarrow & \frac{t}{1-t} = t + t^2 + \ldots\\ 0\verb/*/\; & \leftrightarrow & \frac{1}{1-t} = 1 + t + t^2 + \ldots \end{array}$$ En general, si un patrón permite que un bit se repita $r$ veces, adjuntamos un término $t^r$ a ella.

Combinando estos, obtenemos la siguiente función generadora que corresponde a $(*1)$ .

$$\frac{1}{1-t}\left(\frac{t}{1-t} \frac{t}{1-t}\right)^m\frac{1}{1-t} = \frac{t^{2m}}{(1-t)^{2m+2}} = \sum_{k=0}^\infty \binom{2m+1+k}{k} t^{k+2m} \tag{*2}$$

Si se expande el lado derecho como una serie de potencias de $t$ se encontrarán los términos con poder $t^n$ están en una correspondencia uno a uno con los $n$ -cadenas binarias que coinciden con la expresión regular $(*1)$ . Esto significa que el número que queremos es el coeficiente de $t^n$ en $(*2)$ . es decir

$$\binom{2m+1+(n-2m)}{n-2m} = \binom{n+1}{n-2m} = \binom{n+1}{2m+1}$$

que coincide con lo que obtenemos por otro método.

Answer 2

Tu idea es buena. Un caso es que la cadena empiece por $0$ y termina con $0$ ; en este caso tendrá que subir $m$ tiempos y abajo $m$ veces, empezando con una subida, luego alternando entre bajada y subida, terminando con una bajada. Así que sólo tienes que elegir el $2m$ puntos de conmutación, y hay $\binom{n-1}{2m}$ formas de hacerlo. Dejo los otros casos para ti, como pediste.