Aloha :)
Behauptung
Wir haben eine \(n\)-elementige Menge \(\{1,\ldots,n\}\) gegeben und wählen daraus \(k\)-elementige Teilmengen \(A\) aus. Die Anzahl dieser \(k\)-elementigen Teilmengen soll gleich \(\frac{n!}{k!(n-k)!}\) sein.
Definition des Binomialkoeffizienten
Zum Beweis definieren wir den Binomialkoeffizienten wie folgt:$$\binom{n}{k}\coloneqq\text{Anzahl der Möglichkeiten, aus \(n\) Objekten genau \(k\) auszuwählen.}$$Es ist sofort klar, dass:$$\binom{n}{0}=1\quad;\quad\binom{n}{n}=1\quad;\quad\binom{n}{k}=\binom{n}{n-k}$$
zu 1) Es gibt immer nur eine Möglichkeit, kein Objekt auszuwählen, wir erhalten dann die leere Menge.
zu 2) Es gibt immer nur eine Möglichkeit, alle Objekte auszuwählen.
zu 3) Es gibt genau so viele Möglichkeiten, genau \(k\) Objekte auswählen wie genau \((n-k)\) Objekte nicht auszuwählen.
Aufstellen einer Rekursionsgleichung
Wie viele Möglichkeiten gibt es, aus \((n+1)\) Objekten genau \(k\) auszuwählen? Dazu stellen wir uns vor, wir hätten \(n\) Objekte und würden ein neues Objekt hinzu geben. Dann gibt es 2 Möglichkeiten.
a) Das neue Objekt wird ausgewählt. Dann müssen aus den \(n\) alten Objekten noch genau \((k-1)\) ausgewählt werden. Dafür gibt es \(\binom{n}{k-1}\) Möglichkeiten.
b) Das neue Objekt wird nicht ausgewählt. Dann müssen aus den \(n\) alten Objekten genau \(k\) Objekte ausgewählt werden. Dafür gibt es \(\binom{n}{k}\) Möglichkeiten.
Das bedeutet mit Binomialkoeffizienten geschrieben:$$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$$
Berechnungsformel für den Binomialkoeffizienten
Wir müssen noch zeigen, dass$$\binom{n}{k}=\frac{n!}{k!\cdot(n-k)!}$$
Diese Formel wird oft auch als Definition für den Binomialkoeffizienten verwendet. Wir prüfen die Richtigkeit der Formel, indem wir die Gültigkeit der Randbedingungen und die Gültigkeit der Rekursionsgleichung überprüfen:
$$\binom{n}{0}=\frac{n!}{0!\cdot(n-0)!}=\frac{n!}{1\cdot n!}=1\quad\checkmark\quad;\quad\binom{n}{n}=\frac{n!}{n!\cdot(n-n)!}=\frac{n!}{n!\cdot1}=1\quad\checkmark$$
$$\binom{n}{k}+\binom{n}{k-1}=\frac{n!}{k!\cdot(n-k)!}+\frac{n!}{(k-1)!\cdot(n-(k-1))!}$$$$\qquad=\frac{n!}{k!\cdot(n-k)!}\cdot\frac{(n-k+1)}{(n-k+1)}+\frac{n!}{(k-1)!\cdot(n-k+1)!}\cdot\frac{k}{k}$$$$\qquad=\frac{n!\cdot(n-k+1)}{k!\cdot\underbrace{(n-k)!\cdot(n-k+1)}_{=(n-k+1)!}}+\frac{n!\cdot k}{\underbrace{(k-1)!\cdot k}_{=k!}\cdot(n-k+1)!}$$$$\qquad=\frac{n!\cdot n-n!\cdot k+n!}{k!\cdot(n-k+1)!}+\frac{n!\cdot k}{k!\cdot(n-k+1)!}=\frac{n!\cdot n\,\cancel{-n!\cdot k}+n!\,\cancel{+n!\cdot k}}{k!\cdot(n-k+1)!}$$$$\qquad=\frac{n!\cdot n+n!}{k!\cdot(n-k+1)!}=\frac{n!\cdot(n+1)}{k!\cdot(n+1-k)!}=\frac{(n+1)!}{k!\cdot((n+1)-k)!}=\binom{n+1}{k}\quad\checkmark$$
