Demostrando una combinatoria de identidad: $\sum_{i=0}^m \binom{l}{i}\binom{m+n-l}{m-i} = \binom{m+n}{m}$

Question

Me encontré con la siguiente identidad mientras que el cálculo de ciertas expresiones: $$\sum_{i=0}^m \binom{l}{i}\binom{m+n-l}{m-i} = \binom{m+n}{m}.$$ Aquí, $m,n,l \geq 0$ son fijos y $l \leq m+n$. Asimismo, se asume que $\binom{x}{y} = 0$ siempre $x < y$.

He verificado esta identidad para valores pequeños de $m$, $n$ y $l$, y creo que he venido para arriba con una combinatoria argumento de por qué esta identidad es verdadera. Por favor alguien puede comprobarlo por mí?

---

Prueba.

El lado derecho es el número de maneras de elegir a $m$ objetos de una colección de $m+n$ distintos objetos.

Podemos realizar esta selección en la siguiente forma. Dividir la colección en dos racimos de $l$ objetos y $m+n-l$ objetos. Podemos seleccionar $m$ objetos fuera de nuestro $m+n$ objetos mediante la selección de $i$ objetos de la $l$-bunch y el resto de $m-i$ de la $(m+n-l)$-bunch, para cada posible valor de $i$ $0$ $m$ (en el sentido de que no tratamos de seleccionar más de $l$ objetos fuera de nuestro primer grupo, o más de $m+n-l$ objetos fuera de nuestro segundo racimo). Pero, esto no es sino la expresión en el lado izquierdo.

---

Es mi prueba válida? Estaría agradecido si alguien puede proporcionar pruebas alternas de esta identidad. Gracias de antemano!

Answer 1

Su combinatoria argumento se ve bien. Otra forma es pensar de manera algebraica.

La esencia de su identidad es $(x+1)^{m+n} = (x+1)^l (x+1)^{m+n-l}$.

Para polinomios (o de poder formal de la serie) $F = \sum_i f_i x^i$, $G = \sum_j g_j x^j$ el $m$th coeficiente de operador $[x^m]$ actúa sobre productos de convolución, es decir, $[x^m](FG) = \sum_{i=0}^m F_iG_{m-i}$

El lado derecho de su identidad es el coeficiente de $x^m$$(x+1)^{m+n}$, que por supuesto coincide con el coeficiente de $x^m$$(x+1)^l (x+1)^{m+n-l}$.