Gente sentada alrededor de mesas circulares

Question

Encuentra el número de formas de sentar a n personas A1 , A2 , ..., An en un número arbitrario de mesas circulares de tamaño arbitrario.

Sí, las permutaciones circulares no importan. Por ejemplo, Alrededor de un círculo A,B,C hay tres personas que se sientan como ABC, BCA, CAB en el sentido de las agujas del reloj se consideran equivalentes y se cuentan como una sola configuración.

Y las mesas son indistintas. Por lo tanto, sólo importa la configuración de las personas alrededor de las mesas.

Así es como conté para n = 4:

4 se puede escribir como,

4 = (4-1)! formas = 6 (4 personas alrededor de 1 mesa)

3+1 = (3-1)!*(1-1)! formas = 2 (4 personas alrededor de 2 mesas, etc.)

2+2 = (2-1)!*(2-1)! formas = 1

¡2+1+1 = (2-1)! ¡(1-1)! (1-1)! formas = 1

¡1+1+1+1 = (1-1)! ¡(1-1)! (1-1)! *(1-1)! maneras = 1

por lo que en total sólo he podido contar 11 formas. (¡Quizás esto sea defectuoso de alguna manera? porque otros piensan que el número de configuraciones es n! )

Answer 1

Dejemos que $F(n)$ sea el número de formas de sentarse $n$ personas. Podríamos empezar por cuidadosamente enumerando las formas, para algunos valores pequeños de $n$ . El listado debería ser casi explícito. Encontramos que $F(1)=1$ , $F(2)=2$ , $F(3)=6$ y (quizás) que $F(4)=24$ . A pesar de la escasa cantidad de pruebas, la conjetura $F(n)=n!$ es tentador.

Demostramos la conjetura, en principio por inducción. Supongamos que sabemos que para un determinado $k$ , $F(k)=k!$ . Ahora George, el $(k+1)$ -en la persona, llega, tarde como de costumbre. Para todo lo posible asientos de la $k$ personas, podemos colocar a George en la mesa de uno de los $k$ personas, e inmediatamente a la derecha de esa persona ( $k$ opciones), o podemos colocar a George en una mesa por sí mismo. Así, $$F(k+1)=kF(k)+F(k)=(k+1)F(k)=(k+1)!.$$ Desde $F(1)=1$ concluimos que $F(n)=n!$ para todos $n$ .

Otra forma : Podemos utilizar un lenguaje más elegante. Por ejemplo, observemos que toda permutación del conjunto $\{1,2,\dots,n\}$ puede expresarse de forma única como un producto de ciclos disjuntos. Incluimos explícitamente cualquier $1$ -ciclos. El orden en que se toma el producto no importa, ya que los ciclos son disjuntos.

Todo producto de ciclos disjuntos corresponde a un único asiento circular, y viceversa. (Las personas de un ciclo determinan una mesa, y su orden cíclico determina el orden de los asientos en esa mesa). Esto da una biyección explícita entre las permutaciones de $\{1,2,\dots,n\}$ y los asientos. Así, el número de plazas es igual a $n!$ el número de permutaciones.

Answer 2

Voy a ampliar la segunda forma de André; se puede hacer sin llegar a ser tan técnico como las descomposiciones de ciclos. En cada mesa hay una persona con el número más bajo; llámese a esa persona el líder de esa mesa. Al enumerar las personas de una mesa, empezaremos por el líder y enumeraremos el resto en orden contrario a las agujas del reloj alrededor de la mesa. Con ocho personas y tres mesas, por ejemplo, podríamos tener 3648 alrededor de una mesa, 5 solos en otra y 172 en la tercera. Ahora ordena las listas de las mesas en orden descendente de sus líderes; en mi ejemplo, el 5 va primero, seguido del 3648 y luego del 172. Por último, concatena estas listas para hacer una gran lista con todas las personas de la sala: 53648172.

Es evidente que este procedimiento produce siempre una permutación bien definida de los enteros $1$ a través de $n$ (suponiendo que haya $n$ personas en la sala). Sabemos que hay $n!$ tales permutaciones. Así, si podemos demostrar que el procedimiento es reversible $-$ que de cada posible permutación de $1$ a través de $n$ podemos reconstruir la disposición de los asientos $-$ habremos demostrado que hay $n!$ posibles disposiciones de los asientos.

En lugar de dar un argumento detallado, utilizaré un ejemplo para ilustrar cómo reconstruir la disposición de los asientos a partir de una permutación. Supongamos que $n=9$ y empiezo con la permutación menos aleatoria $694872531$ . Claramente $6$ debe ser un líder de mesa, y de hecho el líder de mesa de mayor número. Escanee la permutación de izquierda a derecha, empezando por el $6$ Siempre y cuando sólo se encuentren números mayores que $6$ deben estar sentados en $6$ pero el primer número menor que $6$ tiene que ser otro líder de la mesa. En este ejemplo eso significa que la lista de la primera mesa debe ser $69$ y $4$ debe ser el líder de la segunda mesa. Continúe de la misma manera: $8$ y $7$ son mayores que $4$ , por lo que deben estar sentados en $4$ de la mesa, pero $2<4$ Así que $2$ debe ser el siguiente líder de la mesa. Ahora tenemos listas para las dos primeras mesas, $69$ y $487$ y sabemos que $2$ es el líder de la tercera mesa. Tras un poco más de trabajo en la misma línea, tenemos el conjunto completo de listas de mesas: $69$ , $487$ , $253$ y $1$ . Estas listas especifican completamente quién está sentado en cada mesa y el orden en el que están sentados alrededor de esa mesa.

Por supuesto, debes terminar convenciéndote de que el procedimiento de listado original y el procedimiento de reconstrucción son realmente inversos, pero eso está bastante claro una vez que entiendes ambos procedimientos.