Utilizando un argumento combinatorio

Question

Estoy teniendo algunas dificultades con este problema:

Utilice un argumento combinatorio para demostrar que $$\binom{m + n}{r} = \binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r - 1} + \dots + \binom{m}{r}\binom{n}{0}$$

Mi libro muestra cómo derivar una identidad, pero no muestra cómo utilizar el argumento para demostrar algo. ¿Cómo puedo demostrar este problema?

Answer 1

Hay varias formas de sacar r bolas entre m+n dependiendo de cuántas saques entre las m y entre las n. (r bolas entre las m, r-1 entre las m y 1 entre las n, ...) El resultado suma cada uno de estos casos para obtener el número total de extracciones.

Answer 2

A la izquierda tienes el número de formas de elegir $r$ elementos de $m + n$ . De todas estas combinaciones puedes dividirlas en grupos según el número $k$ de elementos elegidos que caen en el primer $m$ y los que caen en el último $n$ .

Para cada valor de $k$ tienes $\binom{m}{k}$ de elegir a los $k$ veces $\binom{n}{r-k}$ de elegir el resto. Hay que sumar entre todos $k$ para alcanzar todas las combinaciones, y la identidad se mantiene.

Answer 3

Digamos que tienes m bolas en una caja y n bolas en la otra y las mezclas en un barril.

Tienes que seleccionar r bolas del barril. Las bolas se distinguen pero el orden no es importante. El total de formas en que puedes hacerlo es $\binom{m+n}{r}$

Pero hay otra forma de calcularlo. Considera las cajas de bolas m y n antes de mezclarlas

Puedes elegir 0 de la caja m y r de la caja n o 1 de la caja m y r-1 de la caja n... básicamente k de la caja m y r-k de la caja n para cualquier valor de k de 0 a r.

Así que el número total de formas en que puedes seleccionar r bolas es:

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

El primer y el segundo método son el mismo tipo de selección, pero realizado de forma diferente. Así que tienes:

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

Answer 4

Baraja un mazo de cartas. Dibujar $r$ de ellos. Hay $m=26$ tarjetas con traje negro y $n=26$ tarjetas de color rojo para elegir. El primer término es el número de combinaciones sin negras y todas rojas. El siguiente término es el número de combinaciones con una negra y el resto rojas. Repite la operación hasta que el último término tenga todas rojas y ninguna negra. La suma de todos ellos es el número total de combinaciones de cartas para su $r$ - la mano de la carta.