Verificar la identidad combinatoria siguiente: $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$

Question

$$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$

Niza, por lo que yo he probado algunas identidades combinatorias antes mediante inducción, otras más simples por los modelos de selección del Comité... Pero éste es raro, inducción no incluso parece factible aquí sin cosas que desagradable, y la suma de la izquierda es no facilitar las cosas. ¿Puede alguien ayudarme?

Answer 1

Tenga en cuenta que existen diferentes $m+n$ bolas y dos bolsas.

Una bolsa contiene bolas de $m$ y la otra tiene $n$.

¿Cuál es el número de elegir bolas de $r$? Claramente $$ _{m+n}C_r$ $

Pero divide en dos bolsas. : El número de elección $k$ bolas en la primera bolsa es $ _mC_k $ y debemos elegir bolas de $r-k$ en segunda. El número de posibilidad es $ _nC_{r-k}$ $$ _mC_k\ _nC_{r-k}$ $ eso tenemos

Answer 2

Este es un clásico de la cuenta doble argumento. Vamos a contar cuántas maneras podemos optar $r$ bolas de $m+n$ bolas.

Si colocamos $m+n$ bolas en una sola urna, entonces el lado derecho, se cuenta el número de maneras en que podemos seleccionar $r$ bolas de la urna que contiene $m+n$ bolas.

Supongamos ahora colocamos $m$ bolas en una urna y $n$ bolas en el otro. Puedo seleccionar un total de $r$ cosas de estos dos urnas por la elección de $k$ bolas de la primera urna y $r-k$ bolas de la segunda urna. Por lo tanto, hay $\binom{m}{k}\binom{n}{r-k}$ formas para esta selección a suceder. Sumando sobre todos los posibles valores de $k$ nos dirá el número total de maneras en las que podemos optar $r$ bolas de $m+n$ bolas.

Answer 3

Usando el teorema del binomio, tenemos $$\begin{align} (1+x)^m(1+x)^n &=\sum_{j=0}^m\binom{m}{j}x^j\sum_{k=0}^n\binom{n}{k}x^k\\ &=\sum_{k=0}^{m+n}\color{#C00000}{\sum_{j=0}^k\binom{m}{j}\binom{n}{k-j}}x^k \end {Alinee el} $ y $$\begin{align} (1+x)^{m+n} &=\sum_{k=0}^{m+n}\color{#C00000}{\binom{m+n}{k}}x^k \end {alinee el} $$ comparar los coeficientes de $x^k$.

Answer 4

Aquí está un breve inductivo de la prueba, que sin embargo, puede no ser tan iluminador como una combinatoria argumento:

Teorema. Para todos los números enteros no negativos $r$, $m$ y $n$, no tiene Vandermonde del identidad $$ \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}. $$

Prueba. Deje $f(m,n,r)=\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}$, y el uso de la convenio que $\binom{m}{k}=0$ si $0\leq k\leq m$. Tenga en cuenta que $f(0,n,r)=\binom{n}{r}$. Supongamos ahora que $$ f(m,n,r)=\binom{m+n}{r} $$ fijo $m$, y para todos los $n$$r$. De esta y de la de Pascal, la regla de la $\binom{m+1}{k}=\binom{m}{k-1}+\binom{m}{k}$, nos encontramos con \begin{eqnarray*} f(m+1,n,r)&=&f(m,n,r-1)+f(m,n,r) \\ &=&\binom{m+n}{r-1}+\binom{m+n}{r}=\binom{m+n+1}{r}.\Box \end{eqnarray*}

Answer 5

Forma de proceder es escribir:

$ (x+1)^{m+n} = (x+1)^n*(x+1)^m $

Luego se desarrolla en cada período mediante la fórmula de binomial y evaluar el coeficiente del término $x^r$ a la derecha, sabiendo que el de la izquierda es $C_{n+m}^r$. La prueba es bastante sencilla cuando vas por este camino.

Usted consigue una suma doble con dos índice i, j y para encontrar el coeficiente de $x^r$ tomar cada término que verifica i + j = r.

¿A ayuda?