Problema de Menage Relajado - arreglo de asientos para parejas

Question

El problema original es este:

¿De cuántas maneras se puede sentar a n parejas alrededor de una mesa circular de forma que ninguna pareja se siente al lado de la otra?

Para obtener una respuesta, he mirado la solución aquí:

https://math.dartmouth.edu/~doyle/docs/menage/menage/menage.html

Esto parece ser lo que estoy buscando, pero hay algo que no entiendo.

En la sección "Solución al problema del ménage relajado", no entiendo cómo ha obtenido la ecuación de $d_k$ . ¿Puede alguien explicarlo?

Answer 1

Organizando $k$ fichas de dominó idénticas y no superpuestas en un círculo de $2n$ vértices etiquetados es equivalente a circularmente "elegir" $k$ vértices con al menos $1$ vértice no elegido entre cada par de vecinos: Un vértice "elegido" es el en sentido contrario a las agujas del reloj de cada par de vértices cubiertos por una ficha de dominó.

El número de estos circular "opciones" incluye los vértices $1$ o no:

• Si el vértice $1$ es incluido entonces, ya que no podemos elegir un vértice a ambos lados de $1$ Hay $2n-3$ vértices restantes a partir de los cuales linealmente elija $k-1$ vértices no adyacentes en $\binom{2n-3-(k-2)}{k-1}=\binom{2n-k-1}{k-1}$ formas.
• Si el vértice $1$ no es incluidos entonces hay $2n-1$ vértices restantes a partir de los cuales linealmente elija $k$ vértices no adyacentes en $\binom{2n-1-(k-1)}{k}=\binom{2n-k}{k}$ formas.

Por lo tanto, el número de formas de circularmente elegir $k$ vértices no adyacentes de $2n$ es la suma de estos dos casos exhaustivos y mutuamente excluyentes:

$$\begin{align}d_k&=\binom{2n-k-1}{k-1}+\binom{2n-k}{k}\\[1ex] &=\frac{k}{2n-k}\binom{2n-k}{k}+\binom{2n-k}{k}\\[1ex] &=\left(\frac{k}{2n-k}+1\right)\binom{2n-k}{k}\\[1ex] &=\frac{2n}{2n-k}\binom{2n-k}{k}\tag*{$\blacksquare$}\end{align}$$

según sea necesario.