¿Cuántas cadenas de $8$ Hs y $8$ Ts son tales que hay a lo sumo $2$ ¿Hs consecutivas?

Question

¿Cuántas cadenas de 8 Hs y 8 Ts existen de forma que haya como máximo 2 Hs consecutivas?

No entiendo muy bien cómo enfocar esta cuestión. ¿Cuál sería la forma más rápida de resolverla?

Gracias de antemano.

EDITAR: Un ejemplo de esta secuencia sería (por confusión) $$\text{HHTHHTHHTHHTTTTT}$$

Answer 1

Esta respuesta está bajo la interpretación de que queremos contar las secuencias que evitan el patrón HHH.

Pista: Cada uno de estos arreglos corresponde a una ecuación $a_0 + \cdots + a_8 = 8$ en el que $a_i \in \{0,1,2\}$ . Así que está buscando el coeficiente de $x^8$ en $(1+x+x^2)^9$ que es 2907. Sin utilizar un ordenador, sabemos que las soluciones son de las formas $$(2^0,1^8,0^1),(2^1,1^6,0^2),(2^2,1^4,0^3),(2^3,1^2,0^4),(2^4,1^0,0^5), $$ y así el número total es $$ \binom{9}{0,8,1} + \binom{9}{1,6,2} + \binom{9}{2,4,3} + \binom{9}{3,2,4} + \binom{9}{4,0,5} = \\ 9 + 252 + 1260 + 1260 + 126 = 2907. $$

Answer 2

Si queremos contar el número de secuencias que no contienen HHH,

podemos disponer las T en una fila y dejar que $x_i$ sea el número de H en el hueco i para $1\le i\le 9$ .

Entonces $x_1+\cdots+x_9=8$ con $0\le x_i\le2$ para cada i,

por lo que si dejamos que $A_i$ sea el conjunto de soluciones con $x_i\ge3$ para $1\le i\le9$ y sea S el conjunto de todas las soluciones,

utilizando la Inclusión-Exclusión obtenemos que el número de soluciones integrales viene dado por

$\displaystyle\left|A_1^{c}\cap\cdots\cap A_9^{c}\right|=|S|-\sum_{i}|A_{i}|+\sum_{i<j}|A_i\cap A_j|-\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots$

${\hspace .75 in}=\displaystyle\binom{16}{8}-\binom{9}{1}\binom{13}{8}+\binom{9}{2}\binom{10}{8}=2907$ .

Answer 3

Odio añadir una tercera respuesta, pero como las otras dos no están de acuerdo, supongo que lo haré.

Paso 1: Digamos que tiene $h$ "cabezas-grupos" y $t$ colas; ¿cuántas secuencias se pueden formar sin que haya dos cabezas contiguas? Llamemos a esto $H(h,t)$ . Podemos evaluarlo dividiéndolo en dos casos: Una cola en el último punto, o una cabeza-grupo en el último punto.

Si una cola está en el último lugar, entonces podemos atar una cola al final de cada grupo de cabezas y esto dará $t-h$ colas restantes, por lo que el número de arreglos es $\binom{t-h+h}{h}=\binom{t}{h}$ .

Si un grupo de cabeza está en el último lugar, entonces podemos mirar el resto, y decir que tenemos $h-1$ cabeza-grumos y $t$ colas con el último punto obligado a ser una cola. El número de estos arreglos es $\binom{t}{h-1}$ .

Así, $$ H(t,h) = \binom{t}{h}+\binom{t}{h-1} = \binom{t+1}{h}$$

Paso 2: Si permitimos hasta 2 cabezas consecutivas en un grupo de cabezas, entonces tendremos $t=8$ y 4, 5, 6, 7 u 8 cabezas. Pero si tenemos $c$ de longitud 2, también tendremos $8-2c$ cabezas individuales, o un total de $8-c$ cabeza-grupos. Y aquí hay un punto clave: Podemos distinguir entre las colocaciones de los $c$ longitud 2 grupos entre los que $8-c$ puntos en $\binom{8-c}{c}$ formas. Así, por ejemplo, el número de arreglos con 2 grupos de cabezas de longitud 2 (por tanto, 6 grupos de cabezas en total) será $$ \binom{6}{2} \binom{9}{6} $$

Paso 3: súmalos. La respuesta será $$ \sum_{c=0}^{4} \binom{8-c}{c}\binom{9}{8-c} $$ Este tipo de suma se puede hacer utilizando las técnicas de Concrete Mathematics de Knuth et. al., pero en este caso concreto tenemos $$ \begin{array}{c} \binom{8}{0}\binom{9}{8} + \binom{7}{1}\binom{9}{7} + \binom{6}{2}\binom{9}{6} + \binom{5}{3}\binom{9}{5} + \binom{4}{4}\binom{9}{4} \\ = 1\cdot 9 + 7\cdot 36 + 15\cdot 84 + 10 \cdot 126 + 1\cdot 126 = 2907 \end{array} $$