Demuestra esta identidad con un argumento combinatorio

Question

Demostrar que para todos los enteros $j,k,n, k \ge 0$ tenemos

$$ \sum\limits_{i=0}^n ({-1})^{n-i} \binom {n}{i} \binom {ki}{j} = \begin{cases} 0, & \text{if } 0 \le j < n; \\ k^n, & \text{if } j = n. \end{cases} $$

La suma alterna sugiere el uso del principio de inclusión-exclusión, pero no soy capaz de establecer una situación. La suma se convierte en 0, lo que me resulta extraño. ¿Cómo se incorpora eso? Usando la inclusión-exclusión para contar algo como las funciones surjetivas siempre contamos algo.

Estoy intentando aprender combinatoria, así que preferiría un argumento combinatorio.

Answer 1

Considere $n$ grupos de $k$ objetos. La cantidad ${n\choose i}{ki\choose j}$ representa el número de formas de elegir $i$ de los grupos, luego seleccione $j$ objetos de los grupos elegidos. Por inclusión-exclusión, el lado izquierdo es el número de formas de elegir $j$ total de objetos de una colección de $n$ grupos de $k$ objetos, de manera que cada grupo tenga al menos un objeto seleccionado de él. No es difícil ver que el lado derecho cuenta lo mismo.

Answer 2

Este problema también tiene una prueba algebraica que presento para enriquecimiento. Supongamos que buscamos evaluar

$$\sum_{q=0}^n (-1)^{n-q} {n\choose q} {kq\choose j}.$$

Introducimos

$${kq\choose j} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} (1+z)^{kq} \; dz.$$

Con $j$ no negativo esta integral representa correctamente el coeficiente binomial y desaparece cuando $j$ está fuera de rango. Entonces obtenemos para la suma

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} \sum_{q=0}^n {n\choose q} (-1)^{n-q} (1+z)^{kq} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} (-1+(1+z)^k)^n \; dz.$$

Esto es

$$[z^j] \left({k\choose 1}z + {k\choose 2}z^2 + \cdots + {k\choose k}z^k\right)^n.$$

El primer poder de $z$ que ocurre aquí es $z^n$ por lo que el valor es cero para $j\lt n.$ Además, el coeficiente de $z^n$ sólo puede lograrse de una manera, a saber, tomando el primer término de la suma que se exponenciada. Éste tiene el coeficiente $k$ por lo que la respuesta para $j=n$ es $$k^n.$$

Observación. Podemos utilizar esta técnica para valores mayores de $j.$ Para ejemplo obtenemos para $j=n+2$ el resultado

$${n\choose 1} k^{n-1} {k\choose 3} + {n\choose 2} k^{n-2} {k\choose 2}^2.$$