3.5 Fakultät und Binomialkoeffizienten
Anordnen und Auswählen
Die Fakultät zählt Anordnungen, der Binomialkoeffizient Auswahlen ohne Reihenfolge. Beide Größen sind grundlegend für Kombinatorik, Wahrscheinlichkeitsrechnung und die Analyse von Algorithmen.
Definition 3.8 (Fakultät und Binomialkoeffizient). Für \(n\in\mathbb N\) ist
\[n!:=n(n-1)\cdots2\cdot1,\qquad 0!:=1.\]
Für \(\alpha\in\mathbb R\) und \(k\in\mathbb N\) definieren wir
\[ \binom{\alpha}{k} :=\frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}, \qquad \binom{\alpha}{0}:=1. \]
Für \(n\in\mathbb N_0\) und \(0\le k\le n\) gilt insbesondere
\[\binom nk=\frac{n!}{k!(n-k)!}.\]
Kombinatorische Bedeutung
Für \(k\) geordnete Plätze gibt es zunächst \(n(n-1)\cdots(n-k+1)\) Möglichkeiten. Jede ungeordnete Auswahl wurde darin \(k!\)-mal gezählt, nämlich einmal für jede Reihenfolge ihrer \(k\) Elemente. Division durch \(k!\) entfernt diese Mehrfachzählung.
Beispiel: Testfälle auswählen
Aus \(12\) vorhandenen Testfällen sollen \(4\) für einen schnellen Regressionstest ausgewählt werden. Die Reihenfolge spielt keine Rolle. Wie viele Testmengen sind möglich?
Die folgenden Identitäten ermöglichen rekursive Berechnungen und erklären die Symmetrie des Pascalschen Dreiecks.
Satz 3.6 (Regeln für Binomialkoeffizienten). Für passende \(n,k\) und \(\alpha\) gilt
\[n!=n(n-1)!,\]
\[\binom{\alpha}{k}=\frac{\alpha}{k}\binom{\alpha-1}{k-1}\quad(k\ge1),\]
\[\binom nk=\binom n{n-k},\]
\[\binom nk+\binom n{k+1}=\binom{n+1}{k+1}.\]
Die Additionsregel erzeugt jede innere Zahl aus den beiden darüberliegenden:
\[ \begin{array}{ccccccccccc} &&&&&1&&&&&\\ &&&&1&&1&&&&\\ &&&1&&2&&1&&&\\ &&1&&3&&3&&1&&\\ &1&&4&&6&&4&&1&\\ 1&&5&&10&&10&&5&&1 \end{array} \]
Die Zeile \(n\) enthält \(\binom n0,\binom n1,\ldots,\binom nn\).
Neben den Einträgen selbst verraten auch Diagonalen und Zeilensummen weitere Strukturen im Pascalschen Dreieck.
Zusammenfassung
- \(n!\) zählt die Anordnungen von \(n\) verschiedenen Objekten.
- \(\binom nk\) zählt die \(k\)-elementigen Auswahlen aus \(n\) Objekten ohne Beachtung der Reihenfolge.
- Die Symmetrie \(\binom nk=\binom n{n-k}\) entspricht der Wahl einer Teilmenge oder ihres Komplements.
- Die Additionsregel erzeugt das Pascalsche Dreieck.