El problema:
¿Cuántas secuencias de diez $1's$ y diez $0's$ son posibles de forma que no contengan tres o más ceros consecutivos? (Ej. $00101001001101110011$ )
Sé que hay $20!/10!10!$ secuencias totales. ¿Cómo puedo filtrar las que tienen más de dos ceros consecutivos en alguna parte?
La respuesta puede escribirse como
$${11\choose0}{11\choose10}+{11\choose1}{10\choose8}+{11\choose2}{9\choose6}+{11\choose3}{8\choose4}+{11\choose4}{7\choose2}+{11\choose5}{6\choose0}$$
Es decir, imagina que tienes una cadena de $10$ y ahora tiene que insertar $10$ ceros en dobletes y sencillos. Existen $11$ lugares donde pueden ir los jubilados y los solteros: $9$ lugares entre unos y $2$ lugares en el extremo izquierdo y derecho. Si inserta primero $k$ dobletes, te quedarás con $10-2k$ solteros para insertar, con $11-k$ lugares para insertarlos, por ${11\choose k}{11-k\choose10-2k}$ opciones en total. El número de dobletes puede oscilar entre $0$ a $5$ de ahí la suma.
Observación: La expresión se calcula como $24{,}068$ que es divisible por $547$ como dice el OP (en un comentario debajo de la respuesta de true blue anil) debe ser el caso.
Esta respuesta se basa en la Método de agrupación de Goulden-Jackson .
Consideramos las palabras de longitud $n\geq 0$ construido a partir de un alfabeto $$\mathcal{V}=\{0,1\}$$ y el conjunto $B=\{000\}$ de malas palabras que no pueden formar parte de las palabras que buscamos. Derivamos una función generadora $f(s)$ con el coeficiente de $s^n$ el número de palabras buscadas de longitud $n$ .
Según el documento (p.7) la función generadora $f(s)$ es \begin{align*} f(s)=\frac{1}{1-ds-\text{w}(\mathcal{C})}\tag{1} \end{align*} con $d=|\mathcal{V}|=2$ el tamaño del alfabeto y $\mathcal{C}$ el peso-numerador de malas palabras con \begin{align*} \text{w}(\mathcal{C})=\text{w}(\mathcal{C}[000]) \end{align*}
Calculamos según el documento \begin{align*} \text{w}(\mathcal{C}[000])&=-(sz)^3-sz\cdot \text{w}(\mathcal{C}[000])-(sz)^2\cdot\text{w}(\mathcal{C}[000])\tag{2}\\ \end{align*} donde además marcamos las apariciones de ceros con $z$ . Obtenemos \begin{align*} \text{w}(\mathcal{C})=\text{w}(\mathcal{C}[000])=-\frac{(sz)^3(1-(sz))}{1-(sz)^3} \end{align*}
De (1) y (2) se deduce que \begin{align*} f(s)&=\frac{1}{1-ds-\text{w}(\mathcal{C})}\\ &=\frac{1}{1-(1+z)s+\frac{(sz)^3(1-sz)}{1-(sz)^3}}\\ &=\frac{1+sz+s^2z^2}{1-s-zs^2-z^2s^3}\\ &=1 + (z+1)s + (z+1)^2 s^2 + (3z^2+3z+1)s^3 +\cdots\\ &\qquad+ \left(z^{14}+112z^{13}+\cdots+\color{blue}{24\,068}z^{10}+\cdots+20z+1\right)s^{20}+\cdots\\ \end{align*} La última línea se calculó con ayuda de Wolfram Alpha. El coeficiente de $z^{10}s^{20}$ muestra que de $2^{20}=1\,048\,576$ palabras binarias de longitud $20$ del alfabeto $\{0,1\}$ hay $\color{blue}{24\,068}$ palabras que contienen diez $0$ s y ten $1$ s que no contengan $000$ .
Los diez $1's$ puede considerarse $10$ conformado de barras $11$ "compartimentos" en los que un máximo de dos $1's$ se puede poner.
Esto puede resolverse utilizando estrellas y barras con inclusión-exclusión
$N = \binom{20}{10} - \binom{11}1\binom{17}{10} +\binom{11}2\binom{14}{10} - \binom{11}3\binom{11}{10} = 24068$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
