Contando el número de secuencias con estas propiedades.

Question

La siguiente pregunta fue dada en un examen de la escribí, y me gustaría a ver si alguien puede identificar este tipo de problemas con mi solución. Yo también estaría muy interesado si alguien tiene una solución más elegante.

Nota: si mi solución es demasiado tiempo para mirar por encima, no me importa si usted lo ignora y voluntario de sus propias soluciones a la pregunta.

Pregunta: ¿cuántas secuencias de 21 de moneda gira que consta de 15 colas y 6 jefes de satisfacer las siguientes tres propiedades:

1) el primer y el último tirón de la moneda de los resultados en las colas;

2) no hay apariciones consecutivas de los jefes;

3) cada secuencia de consecutivos colas tiene longitud impar.

A continuación se presenta un esquema de mi solución:

Supongamos que la primera y la última moneda para ver los resultados en una de las colas y contar el número de secuencias, de 19 de moneda gira con 13 colas y 6 cabezas (y ajustar las condiciones anteriores adecuadamente).

Caso #1: Hay una cabeza inmediatamente después de la primera de las colas y de inmediato antes de que el último de la cola. El número de secuencias es dado por el recuento de cuántas maneras podemos elegir el tamaño de la "brecha" entre consecutivos cabezas. Desde que requieren que las sucesivas secuencias de colas han longitud impar, tenemos que la distancia entre los sucesivos jefes son de longitud impar. En particular, se puede tomar los valores de $\{1, 3, 5, 7\}$. La solución de esto es equivalente a la distribución de 13 de objetos idénticos en 5 cajas distintas de tal manera que ningún cuadro está vacío. Este está dado por ${(13-5)+5-1\choose (13-5)}= {12 \choose 8} = {12 \choose 4}$.

Caso #2: Hay una cabeza inmediatamente antes de la última de las colas, pero hay algunos de longitud impar secuencia de consecutivos colas al inicio de la secuencia. Ya hemos arreglado el primero de la cola, debe haber algunos incluso la secuencia de longitud de las colas después de la primera de la cola. Se observa que la longitud de esta secuencia es, en la mayoría de los, 8 (de lo contrario tenemos una ocurrencia consecutivos de cabezas). Así, la longitud de esta secuencia inicial de colas (sin contar el primero de la cola nos revisión) toma valores en $\{2, 4, 6, 8\}$. El número de secuencias de esta forma está dada por: $\displaystyle\sum_{k}{(13-k-5)+5-1\choose (13-k-5)}$ $k \in \{2,4,6,8\}$.

Caso #3: Este caso es el mismo que el anterior, excepto que consideramos que esas secuencias donde hay una cabeza inmediatamente después de la primera de las colas, y de alguna extraña secuencia de longitud de las colas en el final (contando la última de la cola nos revisión).

Caso #4: En este último caso, consideramos que tales secuencias donde hay incluso algunos de longitud de la secuencia de consecutivos colas inmediatamente después de la primera de la cola y de inmediato antes de que el último de la cola. Como por nuestro anterior comentario, estas dos secuencias no puede tener una longitud combinada de más de 8. Así que, a continuación, las posibles longitudes de estos inicial y terminal de las secuencias de los consecutivos de las colas es dada por los pares ordenados $(2,2), (2, 4), (4,2), (4,4)$. Así que, si nosotros índice de estas longitudes, tenemos $j \in \{4, 6, 8\}$, y el número de secuencias es dado por ${(13-j-5)+5-1\choose (13-j-5)}$ por cada $j \in \{4, 6, 8\}$, salvo que por $j=6$ multiplicamos por dos, ya que hay dos posibilidades.

Answer 1

Una manera más simple de verlo es imaginar una cabeza se añade en el extremo izquierdo. A continuación, adjuntar una cola a la derecha de cada cabeza para evitar que dos cabezas en una fila. Conecte el resto de los $8$ colas en cuatro pares, que se puede poner a la derecha de las colas o de otro par. Usted ahora está buscando débil composiciones de cuatro en siete partes. Un estándar de estrellas y barras de cálculo muestra que este es ${7+4-1 \choose 4}=210$

Answer 2

Lamentablemente, este es el problema sin que el hecho de que no hay dos días consecutivos de cabezas.(los malos dejarlo aunque)

Este es el mismo que elegir de 6 cabezas, en un número n de bloques de consecuive cabezas. con la condición de que las distancias entre los bloques ser impar y el primer bloque comienza en una posición.

Supongamos que tenemos un dado de selección de n bloques. De cuántas maneras podemos posición de estos n bloques? la distancia entre cada bloque es de al menos el 2 y el primer bloque está en la posición de al menos 2. También el último bloque debe terminar en una posición. Si elegimos la posición de la cabeza y los espacios entre los bloques, a continuación, hemos terminado. Este es el mismo eligiendo $s_1,s_2,s_3...s_n$ donde $2s_1$ es la posición de la primera cola y $2s_i+1$ es la distancia entre los bloques de $i-1$$i$.

Tenga en cuenta que tenemos la última cabeza en una posición. Comprobar que si la posición de los primeros elementos es 2s_1, a continuación, la posición del último elemento es $2s_1+2s_2+...2s_n+2(n-1)+6=2s_1+2s_2+...2s_n+2n+4$ Significado de esta condición es siempre satisfecho

Así que ahora lo que tiene que contar es el número de listas diferentes de los no enteros negativos$(s_1,s_2,s_3....s_{n})$ tal que $2(s_1+s_2+s_3...+s_n+n+2)\leq20\rightarrow (s_1+s_2+s_3....s_n)\leq8-n$

El uso de las estrellas y las barras de método nos da esto es $\sum_{k=0}^{8-n}\binom{k+n-1}{n-1}$

Y queremos que $\sum_{n=1}^{8}(\sum_{k=0}^{8-n}\binom{k+n-1}{n-1})$

Me tink ti es una identidad para reducir la primera suma, pero no puedo recordar.