Prueba combinatoria de una cierta suma alterna de Coeficientes binomiales

Question

La identidad siguiente apareció como una pregunta anterior hoy

$$\displaystyle\sum\limits_{k=0}^n (-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k} = \begin{cases} 1\ \text{if}\ n=0 \\ 0\ \text{if}\ n>0 \end{cases}$$

y se le dio una solución algebraica. Hay una prueba combinatoria?

Answer 1

Supongamos que usted quiere elegir a $n$ enteros del conjunto $[m+n]$ de tal manera que no incluya cualquier número entero menor o igual a $m+1$. Si $n=0$ esto es posible en exactamente un camino: el que elija el conjunto vacío. Si $n>0$, no es posible, ya que sólo el $n-1$ enteros en $[m+n]\setminus[m+1]$ están disponibles para ser elegido.

Para cada una de las $k\in[m+1]$ deje $\mathscr{A}_k$ el conjunto de $n$-elemento de subconjuntos de a $[m+n]$ que contengan $k$; queremos que el número de $n$-elemento de subconjuntos de a $[m+n]$ que no están en $\bigcup_{k\in[m+1]}\mathscr{A}_k$. Claramente

$$\left|\bigcap_{k\in I}\mathscr{A}_k\right|=\binom{m+n-|I|}{n-|I|}$$

siempre que $\varnothing\ne I\subseteq[m+1]$, así también por la inclusión-exclusión principio hemos

$$\begin{align*} \left|\bigcup_{k\in[m+1]}\mathscr{A}_k\right|&=\sum_{\varnothing\ne I\subseteq[m+1]}(-1)^{|I|-1}\left|\bigcap_{k\in I}\mathscr{A}_k\right|\\ &=\sum_{\varnothing\ne I\subseteq[m+1]}(-1)^{|I|-1}\binom{m+n-|I|}{n-|I|}\\ &=\sum_{k=1}^{m+1}(-1)^{k-1}\binom{m+1}k\binom{m+n-k}{n-k}\;, \end{align*}$$

y de ahí que el número de $n$-elemento de subconjuntos de a $[m+n]$ que no están en $\bigcup_{k\in[m+1]}\mathscr{A}_k$ es

$$\begin{align*} \binom{m+n}n&-\sum_{k=1}^{m+1}(-1)^{k-1}\binom{m+1}k\binom{m+n-k}{n-k}\\ &=\binom{m+n}n+\sum_{k=1}^{m+1}(-1)^k\binom{m+1}k\binom{m+n-k}{n-k}\\ &=\sum_{k=0}^{m+1}(-1)^k\binom{m+1}k\binom{m+n-k}{n-k}\;. \end{align*}$$

Por lo tanto,

$$\sum_{k=0}^{m+1}(-1)^k\binom{m+1}k\binom{m+n-k}{n-k}=\begin{cases} 1,&\text{if }n=0\\ 0,&\text{if }n>0\;. \end{casos}$$

El hecho de que he a $m+1$ en lugar de $n$ como el límite superior de la sumatoria es de poca importancia: en ambas versiones se suma sobre todos los valores de $k$ para que los términos son cero.