Prueba combinatoria del teorema factorial y binomial descendente

¿De cuántas maneras puedes elegir?$k$bolas de un conjunto de$n$diferentes bolas rojas y$m$bolas verdes diferentes?

Respuesta

$$(n+m)^{\underline k}$$

Pero puedes contarlos de otra manera. Supongamos primero que el$k$las bolas son rojas, entonces$k-1$son rojos y$1$es verde, etc

Esto da

$$\sum_{j=0}^k\binom kj n^{\underline j} m^{\underline {k-j}}$$

Prefiero mucho más el argumento combinatorio, pero es útil poder manipular sumas y factoriales descendentes, así que aquí para que conste está el paso de inducción de la prueba por inducción en$k$.

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

Esto también se sigue de la identidad de Vandermonde, es decir

$$\binom{n+m}{k}=\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}$$ que se puede probar usando un argumento tipo comité, a saber, dos formas de elegir un grupo de $k$gente de $n$hombres y $m$mujer. Multiplica ambos lados por $k!$para conseguir eso $$(n+m)^{\underline{k}} =\sum_{i=0}^k\binom{k}{i}n^{\underline i} m^{\underline {k-i}}$$ como se desee.