número de pares formados a partir de$2n$ de personas sentadas en un círculo

Question

Estoy tratando de entender la solución para el siguiente problema:

Supongamos que $2n$ de las personas están sentados en un círculo. De cuántas maneras se pueden formar $n$ de los pares si no al lado dos personas pueden formar una pareja. Exprese su respuesta como una suma finita.

Resulta que la solución es $\displaystyle \sum_{k=0}^n (-1)^k\binom{2n-k}{k}(2n-2k-1)!!$ donde $(2m-1)!!=1\cdot 3\cdot 5\cdots (2m-1)$.

Claramente hay algo de inclusión-exclusión argumento pasando aquí. El primer término de la suma (al$k=0$)$\binom{2n}{0}(2n-1)!!=(1\cdot 3\cdots (2n-1))$. Este es el número de $n$ pares que podemos formar con $2n$ de la gente, ya que la primera persona que ha $2n-1$ opciones, la segunda persona que ha $2m-3$ opciones, etc. No puedo decir lo $\binom{2n-k}{k}$ está contando.

Cualquier ayuda es muy apreciada!

Answer 1

Creo que el binomio plazo, que representa el número de formas de seleccionar $k$ pares adyacentes de personas en un círculo de $2n$ de la gente, en general $(k>0)$ ser $$\left(\binom{2n-k}{k}+\binom{2n-k-1}{k-1}\right)$$

Modelo del círculo de personas con un collar de cuentas negras y blancas, con el elegido de forma arbitraria "primera" persona de las agujas del reloj de la hebilla. Digamos que cada una de las $k$ cuentas negro representa la primera persona (se detectó movimiento de las agujas del reloj) de un par adyacente. Luego, para asegurarse de que no cuentas negro están uno al lado del otro, le pegue una perla blanca a la derecha lado de cada cordón negro.

Ahora hay $2n-k$ piezas móviles, de los cuales, $k$ son pares de perlas.

• Si la primera y la última de las personas en el círculo no son parte de un par, hay $\binom{2n-k}{k}$ maneras de colocar los pares en el collar.

• Si la primera y la última de las personas en el círculo en un par, hay $(2n-2)-(k-1)$ o $2n-k-1$ otras piezas móviles, de los cuales, $k-1$ son parejas.

Para el caso de $k=0$ la fórmula anterior da $\binom{2n}0+\binom{2n-1}{-1}=1+0=1,$ $k=n$ da $2$.

Answer 2

Yo coincido con Andrés Woods en esta pregunta. La correcta coeficiente a utilizar es $$P(n,k) = \left(\binom{2n-k}{k}+\binom{2n-k-1}{k-1}\right)\text{,}$$ el número de maneras de distribuir la $k$ no pares superpuestos en un círculo de $2n$ artículos.

$$\text{Andrew}(n) = \sum_{k=0}^{n} (-1)^k \left(\binom{2n-k}{k}+\binom{2n-k-1}{k-1}\right)(2n-2k-1)!!$$

Esto hace que no se dé el mismo resultado que su fórmula. Por ejemplo, en el $n=3$ donde $4$ asientos son posibles. Andrew correctamente la leche de fórmula calcula esta, pero el tuyo vuelve $5$. Su fórmula está cerca, aunque: $$\text{Andrew}(n) = \text{Sam}(n) - \text{Sam(n-1)}$$

Yo no comprobar que formalmente pero numéricamente se tiene: https://gist.github.com/roSievers/051dc9c7a736e3d959e7

Aquí es otra forma de la razón sobre los $P(n,k)$:

En primer lugar, debemos recordar que hay $\binom{n+k}{k}$ formas para dividir una cadena de longitud $n$ $k$ posición. (división de dos veces en la misma posición en la que está permitido) A contar de las distribuciones par, fijar un índice de "persona" considerar dos casos:

Caso 1: El índice de la persona no es a sí mismos parte de una pareja y $2k$ de las personas en pareja. Luego se divide el restante $2n-2k-1$ personas en $k$ posiciones y un lugar de pares en todos los lugares del corte. $$\binom{2n-2k-1+k}{k} = \binom{2n-k-1}{k}$$

Caso 2: El índice de persona que es, ya sea la izquierda o a la derecha de los miembros de una pareja. I. e. este caso aparece dos veces. Otra de las $2k-2$ de las personas están en los otros pares. El resto de los $2n-2k$ la gente necesita ser dividida en $k-1$ posiciones para insertar pares. $$2\cdot \binom{2n-2k+k}{k-1} = 2 \cdot \binom{2n-k}{k-1}$$

La adición de los casos le da $$P(n,k) = \binom{2n-k-1}{k} + 2 \cdot \binom{2n-k}{k-1} = \binom{2n-k}{k} + \cdot \binom{2n-k}{k-1}\text{.}$$