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.
Respuestas
¿Demasiados anuncios?
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} $$
Markus Scheuer
Puntos
16133
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*>
