Extraño combinatoria de identidad $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0$

Question

Necesito encontrar una combinatoria prueba de esta identidad

$$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0.$$

Creo que la inclusión de la exclusión es el mejor método aquí. Pero estoy teniendo un momento muy difícil viene con un conjunto de contar. Permutaciones no trabajo aquí.

Una sugerencia sería muy bueno. Gracias.

Answer 1

Ha $n$ diferentes pares de zapatos. De cuántas maneras existen para elegir a $n-1$ zapatos para que usted obtenga al menos un zapato de cada par? Obviamente, la respuesta es $0$, pero también se puede utilizar inclusión-exclusión a contar de la manera más difícil de la siguiente manera.

Hay $\binom{2n}{n-1}$ formas de elegir los $n-1$ zapatos. De esto queremos excluir las formas que no incluyen un zapato desde el primer par; claramente hay $\binom{2n-2}{n-1}$ de las personas. Queremos hacer lo mismo para cada una de las $n$ pares, por lo que debemos restar $n\binom{2n-2}{n-1}$. Pero ahora cada una de las $(n-1)$-conjunto que no contiene ningún zapato de cualquiera de los dos primeros pares se ha contado una vez en $\binom{2n}{n-1}$ y resta dos veces en $n\binom{2n-2}{n-1}$ y por lo tanto debe ser agregado en. Hay $\binom{2n-4}{n-1}$ tales $(n-1)$, y lo mismo es cierto para cada par de $\binom{n}2$ pares de pares, por lo que debemos agregar $\binom{n}2\binom{2n-4}{n-1}$.

Continuando de esta manera, vemos que hay

$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{2n-2k}{n-1}$$

conjuntos de $n-1$ zapatos que cumplan con los requisitos, por lo que

$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{2n-2k}{n-1}=0\;.$$

Answer 2

Aquí es una prueba de uso de funciones de generación, un muy buen ejercicio de manipulación de los mismos. La reescritura de la suma de la siguiente manera: $$\sum_{k=0}^n {n\choose k} (-1)^k {2(n-k)\choose n-1}.$$

Observar que cuando multiplicamos dos exponenciales funciones de generación de las secuencias de $\{a_n\}$ $\{b_n\}$ obtenemos que $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\elegir k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ es decir, el producto de las dos funciones de generación es la generación de la función de $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Ahora claramente tenemos en el presente caso que $$A(z) = \sum_{q\ge 0} (-1)^q \frac{z^q}{q!} = \exp(-z).$$ Para $B(z)$ obtenemos que $$B_n(z) = \sum_{q\ge 0} {2q\choose n-1} \frac{z^q}{q!}$$ donde $B_1(z) = \exp(z).$

Con el fin de investigar la $B_n(z)$ presentamos la bivariante de generación de función $$Q(z,w) = \sum_{n\ge 1} B_n(z) w^n = \sum_{n\ge 1} w^n \sum_{q\ge 0} {2t\elegir n-1} \frac{z^p}{q!} = \sum_{q\ge 0} \frac{z^p}{q!} \sum_{n\ge 1} w^n {2t\elegir n-1} \\ = w \sum_{q\ge 0} \frac{z^p}{q!} \sum_{n\ge 1} {2t\elegir n-1} w^{n-1} = w \sum_{q\ge 0} \frac{z^p}{q!} (w+1)^{t2} \\ = w \exp(z (w+1)^2) = \exp(z) \times w \times \exp(z (w^2+2w)).$$ La extracción de los coeficientes de esto nos encontramos con que $$B_n(z) = [w^n] Q(z, w) = \exp(z) [w^{n-1}] \exp(z (w^2+2w)) \\= \exp(z) [w^{n-1}] \exp(z w^2) \exp(2 z w) = \exp(z) \sum_{a+2b=n-1} \frac{2^z^a}{a!} \frac{z^b}{b!}.$$ Esto da lugar a la fórmula $$B_n(z) = \exp(z) \sum_{b=0}^{\lfloor (n-1)/2 \rfloor} \frac{2^{n-1-2b}}{(n-1-2b)! \times b!} z^{n-1-b}.$$

El valor de nuestros suma es, por tanto, $$n! [z^n] A(z) B_n(z) = n! [z^n] \sum_{b=0}^{\lfloor (n-1)/2 \rfloor} . \frac{2^{n-1-2b}}{(n-1-2b)! \times b!} z^{n-1-b} = 0$$ es decir, cero ya que, como se ve fácilmente que el grado del polinomio plazo es $n-1 < n.$

Hay otro cálculo de este tipo en este MSE enlace -- yo y en este MSE link -- II.

Answer 3

Deje $\{S_{i}\}_{i=1}^{n}$ ser una colección de conjuntos de cada uno de tamaño $2$. Doble conteo de conjuntos de $T$ del tamaño de la $n-1$ $\cup S_{i}$ tal que $T$ contiene un elemento de cada una de las $S_{i}$. El lado derecho es claro. Hay $n$ conjuntos y $T$ $n-1$ cosas esto no puede ocurrir nunca. El LHS uso de la EMPANADA.