¿Cuántas cadenas binarias de longitud n >= 4 hay que contienen exactamente dos instancias de 10?

Question

Como se dijo en el título, el orden de 10 importa, por ejemplo para n = 4 solo hay una cadena que es 1010, o para n = 5 hay 6 cadenas como las siguientes: 10101, 10100, 10110, 10010, 11010, 01010 Gracias de antemano.

Answer 1

Imagina los $n$ bits como asteriscos en una línea, marca las transiciones $0\to 1$ como $+$ y las transiciones $1\to 0$ como $-$. Entonces, queremos colocar dos marcas $-$ en las $n-1$ posiciones disponibles, incluyendo una marca $+$ en algún lugar entre ellas, y opcionalmente una marca $+$ en algún lugar antes o después de ellas.

Así que tenemos el siguiente conteo:

$${n-1 \choose 3}+{n-1 \choose 4}+{n-1 \choose 4}+{n-1 \choose 5}= \tag{1}$$ $$={n \choose 4}+ {n \choose 5} \tag{2}$$ $$={n+1 \choose 5} \tag{3}$$

En $(1)$, los números combinatorios corresponden a los patrones permitidos respectivos: $( - + - )$ $(- + - +)$ $( + - + -)$ $( + - + - +)$.

Las ecuaciones $(2)$ y $(3)$ corresponden a la identidad del triángulo de Pascal.

---

Actualización: una formulación equivalente ligeramente más simple sería: colocar un extra $0$ antes de los $n$ bits, y un extra $1$ después de ellos. Entonces, considerando las $n+1$ transiciones disponibles en la cadena expandida de $n+2$, ahora tenemos un único patrón permitido $(+ - + - +)$. Por lo tanto, el conteo total es

$${n+1 \choose 5}$$

Answer 2

Nota: Podemos modelar la situación con funciones generadoras. Pero primero analicemos el problema.

Consideramos cadenas binarias que consisten en $0s$ y $1s$ que contienen precisamente dos subcadenas $10$. Buscamos el número de cadenas con longitud $n\geq 4$. Cada cadena tiene la forma \begin{align*} x10y10z \end{align*> con $x, y, z$ subcadenas de longitud $\geq 0$ que no contienen $10$.

¿Cómo podríamos describir todas las cadenas binarias que no contienen $10$? Son precisamente las cadenas que comienzan con cero o más $0s$, seguidas de cero o más $1s$.

Sea $$1^\star=\{\varepsilon,1,11,111,\ldots\}$$ el conjunto de todas las cadenas que contienen solo $1$s con longitud $\geq 0$. La cadena vacía se denota con $\varepsilon$. La función generadora correspondiente es $$w^0+w^1+w^2+\ldots=\frac{1}{1-w},$$ donde el exponente de $w^n$ marca la longitud $n$ de una cadena de $1s$ y el coeficiente de $w^n$ marca el número de cadenas de longitud $n$. De manera similar definimos $0^\star=\{\varepsilon,0,00,000,\ldots\}$.

Entonces, cada uno de $x, y, z$ en la cadena $x10y10z$ es de la forma $$0^\star1^\star$$ Dado que la concatenación de cadenas corresponde a la multiplicación de las funciones generadoras correspondientes, obtenemos para $x, y, z$ \begin{align*> \left(\frac{1}{1-w}\right)^2 \end{align*> Todas las cadenas binarias que contienen precisamente dos subcadenas $10$ se pueden describir como \begin{align*> (0^\star1^\star)10(0^\star1^\star)10(0^\star1^\star) \end{align*>

Consecuentemente, obtenemos como función generadora \begin{align*> w^4\left(\frac{1}{1-w}\right)^6

Dado que el número de cadenas binarias de longitud $n \geq 4$ está codificado como el coeficiente de $[w^n]$, finalmente obtenemos \begin{align*> [w^n]&w^4\left(\frac{1}{1-w}\right)^6\\ &=[w^{n-4}]\sum_{k=0}^{\infty}\binom{-6}{k}(-w)^k\\ &=\binom{-6}{n-4}(-1)^n\\ &=\binom{n+1}{5}\qquad\qquad n\geq 4 \end{align*>