Tengo problemas para entender cómo la derecha de esta suma es igual a la izquierda. ¡Cualquier información sería útil!
$$\sum_{k=0}^{n} {r \choose k}{s \choose n-k}={r+s \choose n}$$
Respuestas
¿Demasiados anuncios?
En primer lugar, hay un error en la fórmula debería ser $r+s\choose n$ a la derecha. Segundo, he aquí cómo funciona:
Conceptualmente, supongamos que usted ha $r$ objetos en un cubo y $s$ objetos en otro, y desea dibujar $n$ objetos en total entre ellos. De cuántas maneras puede hacerlo?
Bien, es evidente que usted podría simplemente verter todo en un cubo y tome $n$ objetos, así que hay son $r+s\choose n$ formas de hacerlo (es decir, el lado derecho).
O, usted podría dibujar nada desde el primer cubo y $n$ a partir del segundo. Hay ${r \choose 0}{s \choose n}$ maneras de hacerlo.
O usted podría dibujar $1$ cosa que desde el primer cubo y $n-1$ a partir del segundo. Hay ${r \choose 1}{s \choose n-1}$ maneras para que.
O usted podría dibujar $k$ cosas desde el primer cubo y $n-k$ a partir del segundo, para algunos $k \in \{2, \ldots, n\}$. Hay ${r \choose k}{s \choose n-k}$ maneras de hacerlo.
Claramente, una vez que usted haya tratado con todas las posibles combinaciones de dibujo de algún número de la primera cubeta y el resto de la segunda, que ha cubierto todas las combinaciones posibles, en general, por lo que el número total de maneras de seleccionar el $n$ objetos es la suma de todos los anteriores, por lo tanto no se $\sum_{k=0}^n {r \choose k}{s \choose n-k}$ maneras de elegir los objetos, que es el lado izquierdo.
Pero las dos formas de hacer que son equivalentes, de ahí que la igualdad se te ha dado.
Anthony Shaw
Puntos
858
Esto se conoce como Vandermonde de la Identidad. Se dice que para cada forma de elegir a $n$ elementos de un conjunto de $r+s$ elementos, para algunos $k$ debemos optar $k$ a partir del conjunto de $r$ $n-k$ a partir del conjunto de $s$. Esto se traduce en $$ \binom{r+s}{n}=\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}\etiqueta{1} $$
Otra manera de mirar esto es para mirar $$ (1+x)^{r+s}=(1+x)^r(1+x)^s\etiqueta{2} $$ Entonces, usando el Teorema del Binomio, obtenemos $$ \begin{align} \sum_{n=0}^{r+s}\binom{r+s}{n}x^n &=\sum_{i=0}^r\binom{r}{i}x^i\sum_{j=0}^s\binom{s}{j}x^j\\ &=\sum_{n=0}^{r+s}\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}x^kx^{n-k}\\ &=\sum_{n=0}^{r+s}\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}x^n\tag{3} \end{align} $$ La comparación de los coeficientes de $x^n$$(3)$, obtenemos $(1)$.
