Principio de Inclusión y de Exclusión: $2^n = \sum_{i = 0}^n (-1)^i \binom{n}{i} \binom{2n - 2i}{n - 2i}$

Question

Empecé a componer un innecesariamente complicado responder a esta pregunta:

Si tuviéramos 25 personas, todos los que tienen 2 bolas diferentes, ¿cómo podría usted determinar cuántas combinaciones habría si queremos elegir de 25 bolas, pero ninguna persona puede tener tanto de sus bolas en la elección?

La forma más directa es visitar cada una de las veinticinco personas y elegir una pelota para un total de $2^{25}$ opciones. Mi complicada solución hace uso de la inclusión-exclusión de la siguiente manera:

Deje $A_i$ ser el conjunto de todos los 25 de la bola de combinaciones que contienen tanto de la persona $i$'s de bolas. Ya que queremos que el número de maneras en que ninguna persona ha ambos de sus bolas elegido, queremos calcular $$ \binom{50}{25} - \left| \bigcup_{i=1}^{25} A_i \right|. $$ Por el principio de la inclusión y la exclusión, esto se convierte en \begin{align*} \binom{50}{25} - \left| \bigcup_{i=1}^{25} A_i \right| &= \binom{50}{25} - \sum_{i = 1}^{25} (-1)^{i+1} \binom{25}{i} |A_1 \cap \cdots \cap A_i|\\ &= \binom{50}{25} - \sum_{i = 1}^{25} (-1)^{i+1} \binom{25}{i} \binom{50 - 2i}{25 - 2i}\\ &= \sum_{i = 0}^{25} (-1)^i \binom{25}{i} \binom{50 - 2i}{25 - 2i}\\ \end{align*}

Me parece que soy incapaz directamente simplificar este a $2^{25}$ sin apelar a la combinatoria argumento me hizo al principio. Tenga en cuenta que los términos de la suma son todos cero para $i \geq 13$.

Se podría generalizar el problema ligeramente para permitir la $n$ personas cada uno con dos bolas, en cuyo caso obtendremos $$ 2^n = \sum_{i = 0}^n (-1)^i \binom{n}{i} \binom{2n - 2i}{n - 2i}. $$ Hay un no-combinatoria prueba de este hecho que estoy vistas?

Answer 1

Desde $$\binom{2n-2i}{n-2i}=\binom{2n-2i}{n}$$ así

$$\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{2n-2i}{n}=[x^n]\sum_{i=0}^{n}(-1)^i\binom{n}{i}(1+x)^{2n-2i}=[x^n](1+x)^{2n}[1-(1+x)^{-2}]^n\cdot=[x^n]((1+x)^2-1)^n=[x^n]x^n(x+2)^n=2^n$$

Answer 2

Aquí es una solución de uso de variables complejas a veces conocido como el Egorychev método.

Supongamos que buscamos para evaluar $$S(n) = \sum_{q=0}^n {n\elegir q} (-1)^p {2n-2t\elegir n-2t}.$$

Introducir $${2n-2t\elegir n-2t} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n-2t}}{z^{n-2t+1}} \; dz.$$

Esto da por la suma $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \sum_{q=0}^n {n\elegir q} (-1)^q \frac{z^{t2}}{(1+z)^{t2}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \left(1-\frac{z^2}{(1+z)^2}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \left(1+2z\right)^n \; dz.$$

Esta última integral se evalúa a través de una inspección a $$[z^n] (1+2z)^n = {n\choose n} 2^n = 2^n,$$ como se reivindica.

Este MSE enlace apunta a un cálculo similar.