Me encontré con la siguiente resuelto la pregunta en un libro y estoy teniendo dificultades para la comprensión de la respuesta dada por él.
P: Una conferencia es tener ocho presentaciones en el transcurso de un día, que consta de tres presentaciones más largas y cinco cortas presentaciones. Si el organizador de la conferencia no quiere consecutivos largo de las presentaciones, y la conferencia es comenzar con una breve presentación, cómo muchos de los horarios de las presentaciones son posibles?
R: Vamos a S y L un a corto y a largo de la presentación, respectivamente. El horario debe comenzar con una breve presentación, y cada presentación debe ser seguido por al menos una breve presentación. De modo que la programación debe ser SLSLSLS, junto con una breve presentación insertada en algún lugar. Hay cuatro maneras de hacer esto - SSLSLSLS, SLSSLSLS, SLSLSSLS, y SLSLSLSS. Para cada uno de estos hay 5! * 3! posibles horarios, dando un total de 2880 horarios.
Mi análisis dio 7200 horarios en lugar de la siguiente manera.
La primera es fija. Esto deja a cuatro y tres L s a ser permutados con el no-dos-consecutivos-L restricción. O vamos a generalizar a una S y b L. A continuación, el número de compatible permutaciones, que se escribe como N(a, b), puede ser expresado como la recurrencia N(a - 1, b) + N(a - 1, b - 1). La observación de la terminal de valores de N(0, 1) = 1, N(1, 0) = 1, N(1, 1) = 2 y N(0, 2) = 0, y sustituyendo a = 4 y b = 3, el número es de 10. Esto da un total de 10 * 5! * 3! = 7200 horarios.
Lo que me estoy perdiendo?
