Número de asientos circulares si cada persona no puede sentarse junto a otras dos

Question

Hay 30 personas sentadas alrededor de una mesa redonda, y esas 30 personas han llegado al evento en 10 grupos de 3. ¿De cuántas formas diferentes pueden sentarse esas personas alrededor de la mesa si no se permite que nadie se siente al lado de otra persona que haya llegado con ellas (es decir, estaba con ellas en un trío, por lo que por cada persona hay otras dos personas a las que no se les permite sentarse al lado).

Espero que esta explicación tenga sentido.

Estoy realmente perplejo con esta pregunta, completamente perdido y sin idea de por dónde empezar. Sin embargo, mi línea de pensamiento era la siguiente: si se sienta la primera persona, entonces hay 29 personas que aún no se han sentado. Además, hay 2 personas que no puedes sentar en el asiento siguiente, adyacente a la primera persona que sentaste. Así que hay 27 personas que pueden sentarse en el segundo asiento. Luego, en el tercero, quedan 28 personas, ya que se han sentado dos. De nuevo, dos personas no pueden sentarse ahí, ya que hay 26 personas que pueden sentarse en la tercera silla.

Ahora, si mi pensamiento es correcto hasta este punto, las cosas comienzan a volverse particularmente nebulosas en mi mente. Así que quedan 27 personas, y un máximo de dos personas no pueden sentarse en el asiento junto a la tercera persona. Así que parece razonable sugerir que 25 personas pueden sentarse allí. Pero si una de esas dos personas ya se ha sentado antes, entonces en realidad hay 26 de las 27 restantes que pueden sentarse en este asiento. Es aquí donde me encuentro totalmente perdido.

Se me ocurrió que podría calcular el número total posible de disposiciones de asientos sin condiciones, y luego restar las disposiciones en las que la condición dada se rompe....pero eso sería un montón de diferentes condiciones ilegítimas para calcular.

Cualquier ayuda será muy apreciada. Tengo unas cuantas preguntas más como esta para lidiar con aswell después, así que no me importa si usted ayuda, sólo dar pistas, o resolver toda la cosa.

Answer 1

Puede hacerlo a través de inclusión-exclusión pero no veo cómo encontrar una forma cerrada. Vamos a generalizar desde $10$ a $n$ grupos de $3$ . Hay $3n$ condiciones, una para cada uno de los tres pares en cada $n$ grupos. Para formar todas las posibles conjunciones de condiciones, podemos seleccionar $k$ grupos en los que $2$ se cumplen las condiciones y $l$ grupos en los que $1$ se cumple la condición. Para cada uno de los $k$ grupos, hay $3$ formas de seleccionar el $2$ de $3$ condiciones, y para cada una de las $l$ grupos, hay $3$ formas de seleccionar el $1$ de $3$ condiciones; en ambos casos hay $2$ para el miembro del grupo que cumpla las condiciones. Dadas las condiciones cumplidas, quedan $(3n-2k-l-1)!$ posibles órdenes del $3n-2k-l$ bloques de personas, donde restando $1$ explica la simetría cíclica. Si se quiere contar como distintas las configuraciones cíclicamente equivalentes, hay que multiplicar todo el resultado por $3n$ . Así, la inclusión-exclusión da como resultado el número de configuraciones que no cumplen ninguna de las condiciones (y por tanto cumplen las restricciones dadas):

$$ \sum_{k=0}^{10}\sum_{l=0}^{10-k}(-1)^l6^k6^l\binom n{k,l,n-k-l}(3n-2k-l-1)!\;. $$

No veo cómo conseguir una forma cerrada para esto. Para $n=10$ podemos evaluar la suma doble, por ejemplo, en Sage; el resultado es $1038433851912064897405414932480$ .