¿Número de formas de colocar 5 monos en fila?

Question

Tenemos 5 monos $a,b,c,d,e$ y estamos interesados en el número de formas de tenerlos en fila sin $a$ y $b$ estar al lado del otro.

La parte que más me cuesta es que no entiendo muy bien cómo resolver esto cuando los 5 son diferentes. No es lo mismo que, por ejemplo, colorear 5 segmentos de color azul o rojo sin que dos segmentos vecinos sean rojos.

Así es como he intentado resolverlo pero estoy seguro de que hay algo que no funciona. Te agradecería mucho si también pudieras criticar mi planteamiento.

Idea:

Dejemos que $f_{k}$ sea el número de formas en que podemos tener el $5$ monos en una fila sin $a$ y $b$ estar al lado del otro. Intentamos hacerlo de forma recursiva:

caso 1 : el último mono no es $a$ o $b$ : entonces tenemos $f_{k-1}$ posibilidades para el resto de los monos k-1.

caso 2 : el último mono es $a$ o $b$ : Aquí el penúltimo tiene que ser uno de $\{c,d,e\}$ . Así que tenemos $3$ posibilidades para el penúltimo puesto y $2$ posibilidades para el último. Un total de $2*3 = 6$ y $f_{k-2}$ para las plazas restantes.

La ecuación recursiva que obtengo es: $f_{k} = 6 + f_{k-1} + f_{k-2}$

$f_{1} = 5$

$f_{2} = 10$

$f_{3} = 21$

$f_{4} = 37$

$f_{5} = 64$

No estoy seguro de mi solución.

Gracias de antemano

Answer 1

Así es como yo enfocaría este problema en particular. Resolveré para $k$ monos después.

Usted tiene $5!$ formas para que los monos se dispongan en fila sin restricciones.

Hay $8$ formas que $A$ y $B$ pueden colocarse uno al lado del otro; hay $4$ pares de espacios adyacentes y $A$ o $B$ puede estar a la izquierda.

Para cada uno de estos casos, hay $3! = 6$ formas de organizar los otros tres monos.

Así que la respuesta es $5! - 8 \cdot 3! = 72$ formas.

Ahora, sólo hay que aplicar a $k$ monos utilizando el mismo argumento:

$$P(k) = k! - 2(k-1)(k-2)! = k! - 2(k-1)!.$$

(Sugerencia al usuario471297 por la última simplificación).

Answer 2

Solución recursiva (la solución de recuento complementario se expone en la respuesta de John):

Dejemos que $f(k)$ sea el número de formas de organizar $k$ monos, incluyendo $a$ y $b$ de manera que estos dos no estén al lado del otro.

Caso 1: $a$ o $b$ está al principio de la línea.

Contando este caso directamente, primero elegimos el mono principal en uno de $2$ formas. Entonces nos encontramos con que el otro de estos dos monos está en uno de $k-2$ posiciones (cualquier lugar excepto el ocupado por el primer mono, y el inmediatamente posterior). Los otros $k-2$ los monos pueden estar en cualquier orden, por lo que obtenemos $2 (k-2) (k-2)!$ formas.

Caso 2: Ninguno de los dos está al principio de la línea.

Hay un total de $k-2$ opciones para que el mono lidere la línea; después, tenemos la $k-1$ subproblema, por lo que encontramos $(k-2)f(k-1)$ formas aquí.

Combinando estos, tenemos un total de $f(k) = (k-2)(2(k-2)! + f(k-1))$ buenos arreglos. Empezando por $f(2) = 0$ un argumento inductivo debería mostrar que esto coincide con la respuesta de forma cerrada.

Answer 3

@John y @platty han dado buenas respuestas. Aquí hay otro enfoque.

$a$ está en un extremo de la fila: Desde $a$ puede estar en el extremo izquierdo o derecho de la fila, hay dos maneras de colocar $a$ . Para cada una de estas elecciones, hay tres formas de colocar $b$ para que $b$ no es adyacente a $a$ . Los tres monos restantes pueden colocarse en las tres posiciones restantes en $3!$ formas. Por lo tanto, hay $$2 \cdot 3 \cdot 3!$$ acuerdos en los que $a$ está en un extremo de la fila.

$a$ no está al final de la fila: Como hay cinco posiciones incluyendo los dos extremos de la fila, hay tres opciones para la posición de $a$ . Desde $b$ no puede ser adyacente a $a$ Hay dos maneras de colocar $b$ . Los tres monos restantes pueden colocarse en las tres posiciones restantes en $3!$ formas. Por lo tanto, hay $$3 \cdot 2 \cdot 3!$$ acuerdos en los que $a$ no está al final de la fila.

Total: Como los dos casos son mutuamente excluyentes y exhaustivos, los cinco monos se pueden ordenar en $$2 \cdot 3 \cdot 3! + 3 \cdot 2 \cdot 3! = 72$$ maneras si $a$ y $b$ no están en posiciones adyacentes.

Answer 4

He llegado a la respuesta de una manera diferente, no recursiva, que algunas de las respuestas aquí (entiendo que el OP quería una crítica de su enfoque, pero me imaginé que un método diferente todavía podría añadir valor). De todos modos, mi método:

Como dijo John, hay $5!$ formas de organizar los monos sin restricciones. A partir de ahí, traté a los monos $A$ y $B$ como un mono y encontró el número de formas en que el cuatro monos podrían ser arreglados: $4!$

Como hay dos formas de organizar los monos $A$ y $B$ juntos, tienes $2 * 4!$ maneras $A$ y $B$ se podría juntar. Restando del original sin restricciones $5!$ rinde $120 - 2 * 24 = 72$ .

Answer 5

He aquí una solución sencilla:

Primero organiza 5 monos en 5! = 120;

eliminar todos los casos en que tanto a y b se sientan juntos .. así que para conseguir que atar dos monos como un elemento: por lo que tiene 4 monos ahora --- cuántas maneras se puede organizar 4monkeys: 4! y también A y B se sientan como AB y BA así que finalmente

tenemos 2 * 4! formas

entonces: ¡la respuesta es 5! -2 ¡4! así que en general : ¡k! - 2 ¡(k-1)!

¡Ahora sólo hay que ir a las respuestas anteriores k! - 2 * (k-1)(k-2)! también es en realidad lo mismo que k! - ¡- 2* (k-1)!