Aloha :)
Der Binomialkoeffizient \(\binom{n}{k}\) gibt an, wie viele Möglichkeiten es gibt, aus \(n\) Objekten genau \(k\) Objekte auszuwählen (ohne Zurücklegen).
Wir legen ein neues Objekt zu den \(n\) alten Objekten dazu. Wie viele Möglichkeiten gibt es nun, von den \((n+1)\) Objekten genau \(k\) auszuwählen? Wir unterscheiden zwei Fälle:
1) Das neue Objekt wird ausgewählt. Dann müssen aus den \(n\) alten Objekten noch genau \((k-1)\) Objekte ausgewählt werden. Dafür gibt es \(\binom{n}{k-1}\) Möglichkeiten.
2) 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}$$
Für eine Rekursionsgleichung müssen wir uns noch eine Abbruchbedingung überlegen. Es ist klar, dass \(\binom{n}{1}=n\) ist, denn man hat \(n\) Möglichkeiten von \(n\) Objekten genau eins auszuwählen. Die Mathematiker gehen aber noch einen Schritt weiter und sagen, dass es sogar eine Möglichkeit gibt, aus \(n\) Objekten genau keins auszuwählen. In diesem Fall hat man dann die leere Menge in der Hand. Das heißt \(\binom{n}{0}=1\).
Wenn du nun eine Formel suchst, um den Binomialkeoffizienten direkt zu berechnen, kommt dein Ausdruck ins Spiel:$$\binom{n}{k}=\frac{n!}{k!\cdot(n-k)!}$$Man kann nämlich zeigen, dass dieser Ausdruck sowohl die Rekursionsgleichung von oben erfüllt, als auch die Abbruchbedingung \(\binom{n}{0}=1\).
Leider wird in vielen Büchern der Binomialkoeffizient einfach so definiert:$$\binom{n}{k}\coloneqq\frac{n!}{k!\cdot(n-k)!}$$Dabei bleibt dann der Zusammenhang mit der Kombinatorik in der Regel verborgen.
