Contando maneras de asientos parejas, mantener a los hombres aparte, las mujeres aparte, y las parejas aparte

Question

Hay $n$ hombre-mujer de las parejas sentadas alrededor de una mesa, con el número de asiento,$1,2,\dots,2n$. Cuántas formas de sentarse que mantiene a los hombres aparte, las mujeres aparte, y al mismo tiempo las parejas aparte?

Tengo la intención de abordar el problema de la invocación de la Inclusión-Exclusión Principio.

Fije conjunto $$X= \{ \text{sittings that keep men apart and women apart}\}$$

La etiqueta de las parejas con número de $1$, $2$, $\dots$, $n$. Definir $$A_i = \{ \text{sittings that keeps men apart and women apart, but keep the $i$-th couple together} \}$$ para cada una de las $i\in[n]$.

A continuación, el número de sentarse salimos a buscar es igual a: $$\biggl|X-\bigcup_{i=1}^nA_i\biggr|=\biggl|\bigcap_{i=1}^nA_i^c\biggr|$$

El único problema de la izquierda es cómo determinar el tamaño de $A_I$ donde $I$ es un subconjunto de a $[n]$. Pero no tengo idea de cómo enumerar este. Alguien tiene alguna idea?

Answer 1

Esta es sólo una respuesta parcial, que sólo se reduce a esta enumeración de uno a otro.

---

Para una mesa redonda con $n$ asientos, llame a un $(n,k)$de la plantilla de una combinación de la no intersección de los pares de los asientos adyacentes; espero que esta idea va a obtener más clara con la siguiente discusión. Deje $t(n,k)$ el número de $(n,k)$-plantillas; aquí hay una tabla con algunos valores:

$$ \begin{array}{c|ccccc} &0 & 1& 2& 3& 4 \\\hline 1& 1\\ 2& 1& 1\\ 3& 1& 3\\ 4& 1& 4& 2\\ 5& 1& 5& 5\\ 6& 1& 6& 9& 2\\ 7& 1& 7& 14& 7\\ 8& 1& 8& 20& 16& 2\\ 9& 1& 9& 27& 30& 9 \end{array} $$ Aquí hay algunas cosas interesantes sobre ella.

• En la mayoría de los casos, $t(n,k) = t(n-1,k) + t(n-2,k-1)$

• La fila suma (el número de $n$-plantillas) es $n$th Lucas número (con la excepción de $n=2$ por razones obvias).

---

Asumir que el sexo de una persona en la mesa es fija (para evitar la multiplicación por $2$ en todas partes).

A continuación,$|X| = (n!)^2$. Definir $$ B_i = \{\text{las personas sentadas en $i$th y $(i+1)$th asientos son un par}\}. $$ (Me identifico $2n+1$$1$.)

Claramente, $$ \bigl|B_{i_1}\cap B_{i_2}\cap \dots\cap B_{i_k}\bigr| = n\cdot (n-1)\cdots (n-k+1)((n-k)!)^2 = n! (n-k)! $$ (elija las parejas para el asiento de pares, a continuación, sentarse el resto de la gente) siempre que los pares no se cruzan, es decir,$\{i_j,i_j+1\}\cap \{i_l,i_l+1\} = \varnothing$, $j\neq l$; de lo contrario, la intersección es vacía. Pero el número de no-intersección de los pares es exactamente $t(2n,k)$.

Por lo tanto, $$ \biggl|\bigcup_{i=1}^n B_i^c\biggr| = |X| - \sum_{k=1}^n(-1)^{k-1} \sum_{1\le i_1<\dots<i_k\le n} \bigl|B_{i_1}\cap B_{i_2}\cap \dots\cap B_{i_k}\bigr|=\\ = \sum_{k=0}^n (-1)^k t(2n,k) n! (n-k)! = n! \sum_{k=0}^n(-1)^k t(2n,k) (n-k)! $$

Bien, nada muy agradable, pero me parece que la cuestión de enumerar $t(n,k)$ muy interesante por sí misma (Que debe estar relacionada con ciertos problemas de física estadística).

---

Seguir a @torpe comentario, he encontrado aquí que $t(n,k) = \frac{n}{n-k}{n-k\choose k}$ (sin embargo, esto no es totalmente correcto, como $t(2,1) = 1$, no $2$; de lo contrario parece bueno). El enlace también se describe la solución mejor que yo la escribí.