Aloha :)
Die Kernidee des Binomialkoeffizienten
Wir haben \(n\) Objekte und wollen daraus genau \(k\) Objekte (ohne Zurücklegen) auswählen. Die Anzahl dieser Auswahlmöglichkeiten bezeichnen wir mit \(\binom{n}{k}\).$$\binom{n}{k}\coloneqq\text{Anzahl der Möglichkeiten, aus \(n\) Objekten genau \(k\) auszuwählen.}$$
Diese Ausdrücke heißen "Binomialkoeffizienten", man liest sie als "n über k" oder auch "n aus k".
Beispiel
Die Menge \(\{A,B,C,D\}\) enthält \(n=4\) Objekte.
Es gibt genau \(1\) Möglichkeit, kein Objekt auszuwählen, das liefert dann die leere Menge:$$\binom{4}{0}=1\quad\text{nämlich}\quad\{\emptyset \}$$Es gibt genau \(4\) Möglichkeiten, genau ein Objekt auszuwählen:$$\binom{4}{1}=4\quad\text{nämlich}\quad\{\{A\},\{B\},\{C\},\{D\}\}$$Es gibt genau \(6\) Möglichkeiten, genau zwei Objekte auszuwählen:$$\binom{4}{2}=6\quad\text{nämlich}\quad\{\{A,B\},\{A,C\},\{A,D\}\{B,C\},\{B,D\},\{C,D\}\}$$Es gibt genau \(4\) Möglichkeiten, genau drei Objekte auszuwählen:$$\binom{4}{3}=4\quad\text{nämlich}\quad\{\{A,B,C\},\{A,B,D\},\{A,C,D\},\{B,C,D\}\}$$Es gibt genau \(1\) Möglichkeiten, genau vier Objekte auszuwählen:$$\binom{4}{4}=1\quad\text{nämlich}\quad\{\{A,B,C,D\}\}$$
Einfache Folgerungen
$$\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.
Rekursionsgleichung
Wie viele Möglichkeiten gibt es, aus \((n+1)\) Objekten genau \(k\) auszuwählen? Zur Beantwortung stellen wir uns vor, wir hätten \(n\) Objekte und würden dazu ein neues Objekt dazulegen. 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}$$
Pacal-Dreieck
Nachdem wir uns diese Rekursions-Gleichung überlegt haben, können wir die Binomialkoeffizienten für kleine Werte von \(n\) sehr schnell berechnen, indem wir sie in einem Dreieck anordnen:
$$\begin{array}{l}\phantom{\binom{0}{0}}n=0:\\[1ex]\phantom{\binom{0}{0}}n=1:\\[1ex]\phantom{\binom{0}{0}}n=2:\\[1ex]\phantom{\binom{0}{0}}n=3:\\[1ex]\phantom{\binom{0}{0}}n=4:\\[1ex]\phantom{\binom{0}{0}}n=5:\end{array}\quad\begin{array}{c}\binom{0}{0}\\[1ex]\binom{1}{0}\quad\binom{1}{1}\\[1ex]\binom{2}{0}\quad\binom{2}{1}\quad\binom{2}{2} \\[1ex]\binom{3}{0}\quad\binom{3}{1}\quad\binom{3}{2}\quad\binom{3}{3}\\[1ex]\binom{4}{0}\quad\binom{4}{1}\quad\binom{4}{2}\quad\binom{4}{3}\quad\binom{4}{4}\\[1ex]\binom{5}{0}\quad\binom{5}{1}\quad\binom{5}{2}\quad\binom{5}{3}\quad\binom{5}{4}\quad\binom{5}{5}\end{array}\quad\Longleftrightarrow\quad\begin{array}{c}1\\[1ex]1\quad1\\[1ex]1\quad2\quad1 \\[1ex]1\quad3\quad3\quad1\\[1ex]1\quad4\quad6\quad4\quad1\\[1ex]1\quad5\quad10\quad10\quad5\quad1\end{array}$$
Wegen \(\binom{n}{0}=1\) und \(\binom{n}{n}=1\) fängt jede Zeile mit einer \(1\) an und endet mit einer \(1\). Alle Binomialkoeffizienten dazwischen erhalten wir als Summe ihrer beiden Eltern, die über ihm im Dreieck stehen (siehe Rekursions-Gleichung).
Berechnungsformel für den Binomialkoeffizienten
Für große \(n\) ist die Bestimmung von \(\binom{n}{k}\) mit dem Pascal-Dreieck zu aufwendig. Dafür bietet sich die folgende Berechnungsformel an:$$\binom{n}{k}=\frac{n!}{k!\cdot(n-k)!}$$Diese Formel wird oft als Definition für den Binomialkoeffizienten verwendet. Das ist zwar ok, verbirgt aber die Einsicht, was der Binomialkoeffizient wirklich bedeutet. 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$$Damit ist die Gültigkeit der Berechnungsformel bewiesen.
Anwendungsbeispiel: Der binomische Lehrsatz
Ihren Namen haben die Binomialkoeffizienten durch ihr Auftauchen im sog. "binomischen Lehrsatz" erhalten. Wir suchen eine Formel zur schnellen Berechnung von Binomen:$$(a+b)^n=\underbrace{(a+b)\cdot(a+b)\cdot(a+b)\cdots(a+b)}_{n\text{ Faktoren}}$$Bei der Durchführung der Mutliplikation müssen wir aus jedem der \(n\) Faktoren entweder ein \(a\) oder ein \(b\) auswählen.
Wir haben genau \(\binom{n}{n}\) Möglichkeiten, um \(n\)-mal das \(a\) auszuwählen (und kein Mal das \(b\)). Den Beitrag \(a^n\) gibt es also \(\binom{n}{n}=1\) Mal.
Wir haben genau \(\binom{n}{n-1}\) Möglichkeiten, um \((n-1)\)-mal das \(a\) auszuwählen und \(1\)-mal das \(b\). Den Beitrag \(a^{n-1}b\) gibt es also \(\binom{n}{n-1}\) Mal.
Wir haben genau \(\binom{n}{n-2}\) Möglichkeiten, um \((n-2)\)-mal das \(a\) auszuwählen und \(2\)-mal das \(b\). Den Beitrag \(a^{n-2}b^2\) gibt es also \(\binom{n}{n-2}\) Mal.
Führt man diese Argumentation fort, kann man den binomischen Lehrsatz hinschreiben:$$(a+b)^n=\sum\limits_{k=0}^n\binom{n}{n-k}\cdot a^{n-k}\cdot b^k=\sum\limits_{k=0}^n\binom{n}{k}\cdot a^{n-k}\cdot b^k$$
