De cuántas maneras se puede organizar un círculo de socios, de modo que no hay socios están tocando?

Question

Hay un montón de preguntas similares a esta pero ninguno de ellos es el mismo, así que pensé en hacer una nueva pregunta. El problema es que hay un grupo de personas que venían en parejas, en cuántas maneras puede el $N$ a las personas a ser dispuestos en un círculo, de tal manera que no hay persona en el círculo tomados de las manos con la pareja que vino con.

He trabajado a mano, que para dos parejas(cuatro personas) la respuesta es $2$ formas

Para tres parejas ($6$ personas) la respuesta es $32$ formas

También cabe señalar que una rotación del círculo no es contado como un arreglo diferente.

Si la respuesta publica a continuación es correcta la secuencia es OEIS http://oeis.org/A129348 Puede alguien confirmar que esto es correcto?

Answer 1

Sea m el número de parejas, por lo que el $n=2m$.

Sea S el conjunto de todos los asientos de los pares en un círculo, y

deje $E_i$ el conjunto de los asientos en los que par me es juntos, para $1\le i\le m$.

Mediante la Inclusión-Exclusión, y el hecho de que n personas pueden estar sentados en un círculo en $(n-1)!$ formas,

$\displaystyle|\overline{E_1}\cap\cdots\cap\overline{E_m}|=|S|-\sum_{i}|E_i|+\sum_{i<j}|E_i\cap E_j|-\sum_{i<j<k}|E_i\cap E_j\cap E_k|+\cdots+(-1)^m|E_1\cap\cdots\cap E_m|$

$\;=(2m-1)!-\binom{m}{1}2^1(2m-2)!+\binom{m}{2}2^2(2m-3)!-\binom{m}{3}2^3(2m-4)!+\cdots+(-1)^m\binom{m}{m}2^m(m-1)!$

$\;\;=\displaystyle\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}2^{i}(2m-i-1)!$.

Answer 2

Aquí está el cálculo de $8:$

Asiento a una persona de la primera pareja. Esto corrige la rotación del círculo. Asiento de la segunda persona de la primera pareja. El resto de los asientos puede ser en grupos de $1+5 (2$ formas), $2+4 (2$ formas) o $3+3, (1$ manera).

De $1+5$ podemos ir a $4$ en $4$ formas, $1+3$ en $6$ formas, $2+2$ en $2$ formas, $1+1+2$ en $4$ formas, o $1+1+1+1$ en $2$ maneras.
De igual manera nos puede ir de $2+4$ a $1+3$ en $8$ formas o $1+1+2$ en $12$ maneras.
Podemos ir de $3+3$ a $1+3$ en $4$ formas, $2+2$ en $8$ formas, $1+1+2$ en $8$ formas, o $1+1+1+1$ en $2$ maneras.

Multiplicando a cabo después de que dos de las parejas que pueden tener $4$ en $8$ formas, $1+3$ en $32$ formas, $2+2$ en $12$ formas, $1+1+2$ en $40$ formas o $1+1+1+1$ en $6$ maneras.

Finalmente, a partir de $4$ podemos colocar las dos últimas parejas en $8$ formas, $1+3$ en $8$ formas, $2+2$ en $16$ formas, $1+1+2$ en $16$ formas, y $1+1+1+1$ en $24$ maneras.

El total sale $1296$