Personas sentadas alrededor de una mesa que se niegan a sentarse junto a otras dos personas

Question

Iba a generalizar un problema de recuento fácil y acabé sin poder resolverlo:

¿De cuántas maneras puede $n$ personas $1,\dots,n$ sentarse alrededor de una mesa redonda mesa si la persona $i$ se niega a sentarse junto a una persona $i+1$ para todos $i\in\{1,\dots,n-1\}$ y persona $n$ se niega a sentarse junto a la persona 1.

Me he dado cuenta de que tengo que tener $n\geq5$ para tener al menos una solución.

Lo que he hecho:

1. es muy tentador utilizar el principio de inclusión y exclusión, pero no estoy seguro de cómo hacerlo exactamente, ya que se vuelve muy complicado muy pronto. Cualquier ayuda con esto será apreciada.

2. Otra cosa que hice fue utilizar la recursividad, pero todo lo que obtengo es un límite inferior, ya que no soy capaz de analizarlo completamente:

   Si $n-1$ personas están sentadas alrededor de una mesa en $a_{n-1}$ maneras, se puede colocar $n$ entre ellos, excepto el $4$ lugares alrededor de $1$ y $n-1$ . Pero entonces no estamos contando los casos como: $$\dots,2,n,3,\dots$$ Todo lo que dice es que $a_n \geq (n-5)a_{n-1}$ .

   Supongo que debo conectarlo a la caja cuando $i$ se niega a sentarse junto a $i+1$ para $i\in\{1,\dots,n-1\}$ . Pero aún no estoy seguro de cómo.

3. Es sencillo calcular que $a_5=2$ .

PS: ¿Hay alguna relación con el problema del Menage?

Answer 1

Creo que esto es Número de formas de disponer los números 1..n en un círculo de manera que los números adyacentes no difieran en 1 mod n en la Enciclopedia en línea de las secuencias de números enteros. Allí hay un enlace a Número de polígonos que se pueden formar a partir de n puntos de un círculo, sin que haya dos adyacentes que es la mitad del número que queremos. En la última página hay una recurrencia (bastante complicada, no lineal, de 5º orden), y una expansión asintótica en potencias inversas de $n$ . Para la secuencia que nos ocupa, esto comienza $$a_n/(n-1)!\sim e^{-2}(1-(4/n))$$

Answer 2

Una asíntota rápida y sucia: suponiendo una disposición aleatoria, la probabilidad de que la persona en el asiento $k$ encuentra un vecino legal en el asiento $k+1$ es $P(e_k)=(n-3)/(n-1)$ . El caso de que el acuerdo sea legal es $P(e_1 \cap e_2 \cdots)$ . Los eventos $e_k$ no son independientes, pero podemos suponer que asimétricamente podemos escribir

$$P(e_1 \cap e_2 \cdots) = P(e_k)^n=\left(\frac{n-3}{n-1}\right)^n = \left(1- \frac{2}{n} -\frac{2}{n^2} + O(n ^{-3})\right)^n \to e^{-2}$$

Así que $$a_n \to (n-1)! \, e^{-2}$$