Para la cena, vinieron nnn personas y se sentaron en una mesa redonda al azar. Si Ana, Iván y Mark estuvieran entre ellos, ¿de cuántas maneras podrían sentarse para...

Método 1: Marca de asiento. Lo usaremos como nuestro punto de referencia.

Solo Ana se sienta al lado de Mark : Se puede sentar de dos maneras, a su izquierda oa su derecha. Eso deja$n - 2$asientos. Como Iván no puede sentarse al lado de Ana o Mark, puede sentarse en$n - 4$maneras. El restante$n - 3$las personas pueden sentarse en el resto$n - 3$asientos en$(n - 3)!$formas a medida que avanzamos en el sentido de las agujas del reloj alrededor de la mesa en relación con Mark. Por lo tanto, hay$2(n - 4)(n - 3)!$tales arreglos.

Solo Iván se sienta al lado de Mark : Por simetría, hay$2(n - 4)(n - 3)!$tales arreglos.

Tanto Ana como Iván se sientan al lado de Mark : Hay dos formas de sentar a Ana, a la izquierda oa la derecha de Mark. Ivan debe sentarse al otro lado de Mark. El restante$n - 3$las personas pueden sentarse en el resto$n - 3$asientos en$(n - 3)!$formas a medida que avanzamos en el sentido de las agujas del reloj alrededor de la mesa en relación con Mark. Por lo tanto, hay$2(n - 3)!$dichos arreglos de asientos.

Total: Dado que los tres casos son mutuamente excluyentes y exhaustivos, el número de asientos admisibles es

$$\begin{align*} 2(n - 4)(n - 3)! + 2(n - 4)(n - 3)! + 2(n - 3)! & = [4(n - 4) + 2](n - 3)!\\ & = (4n - 14)(n - 3)! \end{align*}$$

Método 2: Marca de asiento. Lo usaremos como nuestro punto de referencia.

Elige si Ana o Iván se sientan a su lado. Elija de qué lado de Mark se sienta esa persona. Asiento el resto$n - 2$personas a medida que avanzamos en el sentido de las agujas del reloj alrededor del círculo relativo a Mark. Esto da

$$2 \cdot 2 \cdot (n - 2)! = 4(n - 2)!$$ disposición de los asientos.

De estos, hay que restar aquellos arreglos en los que Ana e Iván se sientan uno al lado del otro. Para que esto suceda, ambos deben sentarse del mismo lado de Mark. Elige cuál de ellos se sienta al lado de Mark. Elija de qué lado de Mark se sienta esa persona. Si esa persona es Ana, solo hay una forma de sentar a Iván junto a ella, ya que Mark está al otro lado. Del mismo modo, si Iván se sienta junto a Mark, solo hay una forma de sentar a Ana junto a Iván, ya que Mark está del otro lado. Una vez que se hayan ocupado esos tres asientos, asiente el resto$n - 3$personas en el resto$n - 3$asientos a medida que avanzamos en el sentido de las agujas del reloj alrededor de la mesa. Hay

$$2 \cdot 2 \cdot (n - 3)! = 4(n - 3)!$$ dichos arreglos de asientos.

También debemos restar aquellas disposiciones de asientos en las que tanto Ana como Iván se sientan al lado de Mark ya que los hemos contado dos veces en nuestro conteo inicial, una cuando designamos a Ana como la persona que se sienta al lado de Mark y otra cuando contamos a Iván como la persona que se sienta al lado de Mark. Como mostramos arriba, hay

$$2(n - 3)!$$ disposición de los asientos en la que tanto Ana como Iván se sientan junto a Mark.

Por lo tanto, el número de arreglos de asientos admisibles es

$$4(n - 2)! - 4(n - 3)! - 2(n - 3)! = [4(n - 2) - 4 - 2](n - 3)! = (4n - 14)(n - 3)!$$

Primero considere solo los arreglos de A, M e I.

Hay$2$arreglos para que los tres estén juntos ya que M debe estar en el medio.

Hay$4(n-4)$arreglos para que solo dos estén juntos ya que elegimos uno de A y I para estar en uno u otro lado de M y luego colocamos el tercero de ellos en uno de$n-4$asientos.

Por lo tanto, tenemos$4n-14$arreglos para las personas nombradas y para cada uno de estos arreglos hay$(n-3)!$arreglos de los invitados restantes; un total de$(4n-14)(n-3)!$preparativos.

Los tipos de posibilidades para Ana, Mark, Ivan y$n-3$Las sillas vacías se pueden escribir como

1. $AMI-$
2. $IMA-$
3. $AM-I-$
4. $MA-I-$
5. $IM-A-$
6. $MI-A-$,

dónde$-$indica una fila de al menos una silla. Cada configuración corresponde a$(n-3)!$asientos, teniendo en cuenta la colocación de los restantes$n-3$gente en sillas. 1. y 2. son configuraciones únicas (la fila de sillas tiene una longitud$n-3$); los elementos restantes corresponden a$n-4$configuraciones cada uno, ya que la longitud de la primera fila de sillas puede ser$1,2,\ldots,n-4$. Entonces el total es

$$(n-3)!\cdot(2 + 4\cdot(n-4)) = (4n-14)(n-3)!$$

Dejar$A$representan el número de arreglos de asientos cuando Ana está al lado de Mark o Ivan está al lado de Mark, pero no ambos. Si$n \ge 5$no es dificil demostrar que

$\tag 1 A = 4 (n-3) (n-4) \,(n-4)!$

el factor de$4 = 2 \times 2$se obtiene doblando para el enlace Ana/Iván y el enlace izquierda/derecha. El restante$n - 2$factores resultan de aplicar la regla del producto mientras se asienta el resto$n - 2$personas (la última persona sentada corresponde a un factor de$1$). Pero$A = 0$cuando$n = 4$y entonces$\text{(1)}$también proporciona el conteo correcto para$n \ge 4$.

Dejar$B$representan el número de arreglos de asientos cuando Ana e Iván están al lado de Mark. No es difícil demostrar que

$\tag 2 B = 2 \,(n-3)!$

el factor de$2$se obtiene doblando por el enlace Ana/Iván que también incorpora, a su vez, el enlace izquierda/derecha. Nuevamente, sentamos a cada una de las personas restantes mientras usamos la regla del producto.

Empleando álgebra calculamos

$\tag 3 A + B = (4n - 14) \, (n - 3)!$

Compare la técnica anterior con el Método 1 de NF Taussig (una ligera diferencia).

También podemos encontrar la respuesta utilizando técnicas recursivas.

Este problema solo tiene solución cuando$n \ge 4$. Para$n \ge 4$definir

$\quad A(n) = \text{the number of solutions where Mark IS NOT next to BOTH Ana and Ivan.}$

$\quad B(n) = \text{the number of solutions where Mark ---IS---- next to BOTH Ana and Ivan.}$

queremos encontrar la suma$C(n) = A(n) + B(n)$.

Podemos insistir en que nuestro algoritmo de conteo de asientos se logra sentando a una sola persona a la vez en la multiplicidad existente de arreglos de asientos a medida que "llegan". Además, las tres primeras personas en llegar son Mark, Ana e Ivan.

Así que cuando llega la cuarta persona tenemos

$\quad A(4) = 0 \text{ and } B(4) = 2$

disposición de los asientos.

Supongamos que tenemos una lista de todos los arreglos de asientos para$n$gente, y ahora tenemos que sentar al siguiente$(n+1)^{\text{th}}$persona. Usando argumentos combinatorios/de conteo, se puede demostrar que

$\tag A A(n+1) = (n-1)A(n) + 4B(n)$

y

$\tag B B(n+1) = (n-2) B(n)$

---

Lo divertido de los problemas combinatorios es que a menudo se pueden resolver de varias maneras y luego puedes confirmar la respuesta cuando las diferentes soluciones dan el mismo resultado. El lector interesado puede trabajar en lo siguiente:

Ejercicio: Usando inductina, muestre que el modelo recursivo discutido aquí da los mismos resultados que los métodos de disposición de asientos encontrados en esta respuesta .

---

También es posible derivar la respuesta de la fórmula cerrada a partir de este modelo recursivo; consulte esto .