Kombinatorischer Beweis des fallenden Fakultäts- und Binomialsatzes

Wie viele Möglichkeiten können Sie auswählen$k$Bälle aus einer Reihe von$n$verschiedene rote Bälle und$m$grüne verschiedene Bälle?

Antworten

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

Aber man kann sie auch anders zählen. Nehmen wir zunächst an, dass die$k$Kugeln sind dann rot$k-1$sind rot u$1$ist grün usw.

Das gibt

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

Ich bevorzuge das kombinatorische Argument, aber es ist nützlich, Summationen und fallende Fakultäten manipulieren zu können, also hier fürs Protokoll der Induktionsschritt des Beweises durch Induktion$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*}$$

Dies folgt auch aus der Identität von Vandermonde, dh

$$\binom{n+m}{k}=\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}$$ was mit einem komiteeähnlichen Argument bewiesen werden kann, nämlich zwei Möglichkeiten, eine Gruppe von auszuwählen $k$Menschen von $n$Mann und $m$Frauen. Multiplizieren Sie beide Seiten mit $k!$um das zu bekommen $$(n+m)^{\underline{k}} =\sum_{i=0}^k\binom{k}{i}n^{\underline i} m^{\underline {k-i}}$$ wie gewünscht.