Número de formas de sentar a los estudiantes en una mesa redonda con ciertas condiciones.

Question

En una competición olímpica, hay $n$ equipos. Cada equipo está compuesto por $k$ estudiantes que asisten a diferentes asignaturas. ¿Cuántas formas hay de sentar a todos los estudiantes en una mesa redonda de manera que $k$ ¿los alumnos de un equipo se sientan juntos y no hay dos alumnos que cursen la misma asignatura sentados uno al lado del otro?

Mi intento:

Dejemos que $S_n$ denotan la forma total de sentar a todos los estudiantes en $n$ equipos con $k$ estudiantes de cada equipo de manera que se satisfaga el problema.

Entonces descubro que $\forall n \geq 2$ $S_{n+1}=\alpha.nS_n$ con $\alpha = 2(k-1)!-(k-2)!$ Pero hay un problema para mí para encontrar $S_2$ porque puede ser no relativo a $S_1$ . ¡Ayúdenme!

Answer 1

Me encontré con un problema así en un concurso hace años. Tienen las soluciones así que os pongo el enlace. Mira la pregunta 10:

http://www.cemc.uwaterloo.ca/contests/past_contests/2009/2009EuclidContest.pdf (cuestionario)

http://www.cemc.uwaterloo.ca/contests/past_contests/2009/2009EuclidSolution.pdf (solución)

No era necesario derivar una fórmula para responder a la pregunta, pero en alguna parte de la solución dan la fórmula explícita.

Answer 2

Creo que tu recurrencia no es del todo correcta. Si empiezas con un arreglo aceptable de $n$ equipos, puede insertar un $(n+1)$ -en cualquiera de los equipos de $n$ ranuras entre equipos adyacentes. Los miembros del nuevo equipo pueden permutarse en $k!$ formas; $(k-1)!$ de estos tienen una persona inaceptable en un extremo, $(k-1)!$ tener una persona inaceptable en el otro extremo, y $(k-2)!$ tienen una persona inaceptable en ambos extremos, así que

$$S_{n+1}=n\Big(k!-2(k-1)!+(k-2)!\Big)S_n\;,$$

es decir, deberíamos tener $\alpha=k!-2(k-1)!+(k-2)!$ .

Ahora asumo que los arreglos que difieren sólo por una rotación de la mesa se consideran iguales. Entonces $S_1=(k-1)!$ . Hay al menos dos maneras de ver eso $S_2=k!\alpha$ .

1. Comience con cualquiera de los $(k-1)!$ disposiciones de un equipo. Hay $k$ ranuras en las que podemos insertar el segundo equipo, y el argumento dado anteriormente muestra que dentro de su ranura se puede organizar en $\alpha$ formas, para un total de $(k-1)!k\alpha=k!\alpha$ arreglos.
2. Hay $k!$ formas de asentar el primer equipo alrededor de la mitad de la tabla, y por el argumento dado anteriormente hay $\alpha$ maneras aceptables de sentar al segundo equipo alrededor de la otra mitad de la mesa.

Combina esto con la recurrencia $S_n=(n-1)\alpha S_{n-1}$ para $n\ge 3$ y se puede obtener fácilmente una expresión cerrada para $S_n$ en términos de $n$ y $k$ .