Nachlesen

Binomialkoeffizient

Beim Binomialkoeffizient handelt es sich um eine mathematische Funktion, mit der eine der Grundaufgaben der Kombinatorik gelöst werden kann, nämlich die Frage nach der Anzahl der Möglichkeiten, aus einer Menge von \(n\) unterscheidbaren Elementen insgesamt \(k\) Elemente auszuwählen, wobei kein Element mehrfach verwendet wird und die Auswahlreihenfolge keine Rolle spielt – also Ziehen ohne Zurücklegen und ohne Reihenfolge. Der Binomialkoeffizient beschreibt somit die Anzahl der \(k\)-elementigen Teilmengen in der Potenzmenge einer \(n\)-elementigen Menge.

Die Bezeichnung Binomialkoeffizient geht auf die Eigenschaft zurück, dass es sich um die Koeffizienten im namensgebenden binomischen Lehrsatz handelt.

Inhalt

Definition
Darstellung im Pascalschen Dreieck
Herleitung
Beweise
Verallgemeinerung

Definition

Explizite Form

Für zwei natürliche Zahlen \(n,k \in \N_0\) mit \(n \geq k\) beschreibt der Binomialkoeffizient \(n\) über \(k\) die Anzahl der Möglichkeiten, aus einer \(n\)-elementigen Menge eine \(k\)-elementige Teilmenge auszuwählen. Der Binomialkoeffizient \(\binom{n}{k}\) ist definiert durch

\binom{n}{k} = \frac{n!}{(n-k)! \cdot k!}.

Bei \(n!\) handelt es sich hierbei um die Fakultät.

Rekursionsformel der Binomialkoeffizienten

Für zwei natürliche Zahlen \(n,k \in \N_0\) mit \(n \geq k\) kann der Binomialkoeffizient \(\binom{n}{k}\) auf die folgende Art rekursiv definiert werden:

\begin{align*} \binom{n}{0} &= 1 = \binom{n}{n} \quad(\text{für alle } n \geq 0) \\[0.5em] \binom{n}{k} &= \binom{n-1}{k-1} + \binom{n-1}{k} \quad(\text{für } n \gt 0 \text{ und } 0 \lt k \lt n). \end{align*}

Symmetrie der Binomialkoeffizienten

Für zwei natürliche Zahlen \(n,k \in \N_0\) mit \(n \geq k\) gilt stets

\binom{n}{k} = \binom{n}{n-k}.

Darstellung im Pascalschen Dreieck

Hauptartikel: Pascalsches Dreieck

Die Binomialkoeffizienten lassen sich elegant mit dem sogenannten Pascalsches Dreieck darstellen. Hierbei bildet der Binomialkoeffizient \(\binom{n}{k}\) den \(k\)-ten Eintrag in der \(n\)-ten Zeile des Pascalschen Dreiecks, wobei Zeilen- und Eintragsnummer jeweils bei 0 beginnend gezählt werden.

\begin{array}{ccccccccccccccccc} &&&&&1&&&&&\\[0.5em] &&&&1&&1&&&&\\[0.5em] &&&1&&2&&1&&&\\[0.5em] &&1&&3&&3&&1&&\\[0.5em] &1&&4&&6&&4&&1&\\[0.5em] 1&&5&&10&&10&&5&&1 \end{array}

Es ist gut zu erkennen, dass alle äußeren Einträge, die immer die Anzahl der Möglichkeiten zur Auswahl von keinem bzw. von allen Elementen darstellen, den Wert \(1\) haben. Für alle inneren Einträge gilt, dass sie stets die Summe der beiden diagonal darüberliegenden Werte sind – dies ist eine direkte Veranschaulichung der Rekursionsformel. Zudem ist jede Zeile von vorne nach hinten bzw. von hinten nach vorne gelesen stets identisch; dies entspricht der Symmetrie der Binomialkoeffizienten.

Dasselbe Dreieck noch einmal mit den nicht ausgerechneten Binomialkoeffizienten \(\binom{n}{k}\).

\begin{array}{ccccccccccc} &&&&&\binom{0}{0}&&&&& \\[0.5em] &&&&\binom{1}{0}&&\binom{1}{1}&&&& \\[0.5em] &&&\binom{2}{0}&&\binom{2}{1}&&\binom{2}{2}&&& \\[0.5em] &&\binom{3}{0}&&\binom{3}{1}&&\binom{3}{2}&&\binom{3}{3}&& \\[0.5em] &\binom{4}{0}&&\binom{4}{1}&&\binom{4}{2}&&\binom{4}{3}&&\binom{4}{4}& \\[0.5em] \binom{5}{0}&&\binom{5}{1}&&\binom{5}{2}&&\binom{5}{3}&&\binom{5}{4}&&\binom{5}{5} \end{array}

Herleitung

Herleitung der expliziten Formel

Gegeben seien zwei natürliche Zahlen \(n,k \in \N_0\) mit \(n \geq k\). Um die Frage zu beantworten, wie viele Möglichkeiten es gibt, aus einer Menge mit \(n\) unterscheidbaren Elementen genau \(k\) verschiedene Elemente auszuwählen, wobei die Auswahlreihenfolge keine Rolle spielt, wird zunächst die Frage beantwortet, wie viele Möglichkeiten es gibt, \(k\) verschiedene Elemente unter Berücksichtigung der Reihenfolge auszuwählen: Für das erste Element gibt es insgesamt \(n\) Möglichkeiten. Da kein Element doppelt verwendet werden darf, muss das zweite Element aus den verbleibenden \(n-1\) Elementen ausgewählt werden; hierfür gibt es genau \(n-1\) Möglichkeiten. Das dritte Element muss nun aus den verbleibenden \(n-2\) Elementen gewählt werden. Dies wird solange wiederholt, bis schließlich das \(k\)-te Element aus den verbleibenden \(n-k+1\) Elementen ausgewählt wurde. Insgesamt ergeben sich somit

n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = n^\underline{k} = \frac{n!}{(n-k)!}

Möglichkeiten, genau \(k\) der \(n\) Elemente auszuwählen – allerdings unter Berücksichtigung der Reihenfolge. Mit \(n^\underline{k}\) ist hierbei die \(k\)-te fallende Faktorielle von \(n\) bezeichnet. Um die ursprüngliche Frage nach der Anzahl der Möglichkeiten ohne Berücksichtigung der Reihenfolge zu beantworten, muss nun also überlegt werden, wie oft dieselben Elemente \(a_1,\ldots,a_k\) (in unterschiedlicher Reihenfolge) ausgewählt wurden. Dies kann über die Anzahl der Permutationen einer \(k\)-elementigen Menge direkt beantwortet werden: Es gibt \(k!\) Möglichkeiten, \(k\) unterscheidbare Elemente anzuordnen.

Um die gesuchte Anzahl der Möglichkeiten zur Auswahl von \(k\) Elementen ohne Berücksichtigung der Reihenfolge zu beantworten, muss die zuvor erhaltene Zwischenlösung \(n^\underline{k}\) um die Anzahl der Permutationen einer \(k\)-elementigen Menge bereinigt werden, woraus sich unmittelbar die explizite Definition der Binomialkoeffizienten ergibt:

\binom{n}{k} = \frac{n^\underline{k}}{k!} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{(n-k)! \cdot k!}

Herleitung der Rekursionsformel

Gegeben seien zwei natürliche Zahlen \(n,k \in \N_0\) mit \(n \geq k\). Die Frage, wie viele Möglichkeiten zur Auswahl von \(k\) verschiedenen Elementen einer \(n\)-elementigen Menge ohne Berücksichtigung der Auswahlreihenfolge es gibt, kann direkt auf die äquivalente Frage zurückgeführt werden, wie viele \(k\)-elementige Teilmengen einer \(n\)-elementigen Menge es gibt.

Zunächst werden zwei Spezialfälle betrachtet. Um aus einer \(n\)-elementigen Menge genau \(k=0\) Elemente auszuwählen, gibt es exakt eine Möglichkeit; dasselbe gilt, falls aus einer \(n\)-elementigen Menge alle \(n\) Elemente ausgewählt werden sollen:

\binom{n}{0} = 1 = \binom{n}{n}.

Für den allgemeinen Fall mit \(n \gt 0\) und \(0 \lt k \lt n\) gilt: Betrachtet man eine \(n\)-elementige Menge \(A\) und ein beliebiges Element \(a \in A\) dieser Menge, dann lassen sich die \(k\)-elementigen Teilmengen von \(A\) in zwei Kategorien aufteilen:

Teilmengen, in denen das Element \(a\) enthalten ist. In diesem Fall sind neben dem Element \(a\) also noch \(k-1\) weitere Elemente aus der Menge \(A \setminus \bigl\{ a \bigr\}\) in der Teilmenge enthalten. Um diese \(k-1\) Elemente auszuwählen gibt es \(\binom{n-1}{k-1}\) Möglichkeiten.
Teilmengen, in denen das Element \(a\) nicht enthalten ist. In diesem Fall kommen alle \(k\) Elemente der Teilmenge aus der Menge \(A \setminus \bigl\{ a \bigr\}\). Um diese \(k\) Elemente auszuwählen gibt es \(\binom{n-1}{k}\) Möglichkeiten.

Als Zusammenfassung dieser beiden Fälle ergibt sich für die Anzahl der \(k\)-elementigen Teilmengen von \(A\) – und somit auch für die Anzahl der Möglichkeiten, \(k\) verschiedene Elemente ohne Berücksichtigung der Reihenfolge auszuwählen – die folgende Formel, bei der es sich um die Rekursionsformel der Binomialkoeffizienten handelt:

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.

Beweise

Beweis der Rekursionsformel

Für natürliche Zahlen \(n,k \in \N_0\) kann die rekursive Definition der Binomialkoeffizienten durch Nachrechnen gezeigt werden.

\begin{align*} \binom{n-1}{k-1} + \binom{n-1}{k} &\overset{(1)}{=} \frac{(n-1)!}{\bigl((n-1)-(k-1)\bigr)! \cdot (k-1)!} + \frac{(n-1)!}{\bigl((n-1)-k\bigr)! \cdot k!} \\[0.75em] &\overset{(2)}{=} \frac{(n-1)!}{(n-k)! \cdot (k-1)!} + \frac{(n-1)!}{(n-k-1)! \cdot k!} \\[0.75em] &\overset{(3)}{=} \frac{k \cdot (n-1)!}{k \cdot (n-k)! \cdot (k-1)!} + \frac{(n-k) \cdot (n-1)!}{(n-k) \cdot (n-k-1)! \cdot k!} \\[0.75em] &\overset{(4)}{=} \frac{k \cdot (n-1)!}{(n-k)! \cdot k!} + \frac{(n-k) \cdot (n-1)!}{(n-k)! \cdot k!} \\[0.75em] &\overset{(5)}{=} \frac{k \cdot (n-1)! + (n-k) \cdot (n-1)!}{(n-k)! \cdot k!} \\[0.75em] &\overset{(6)}{=} \frac{(n-1)! \cdot \bigl(k + (n-k)\bigr)}{(n-k)! \cdot k!} \\[0.75em] &\overset{(7)}{=} \frac{(n-1)! \cdot n}{(n-k)! \cdot k!} \\[0.75em] &\overset{(8)}{=} \frac{n!}{(n-k)! \cdot k!} \\[0.75em] &\overset{(9)}{=} \binom{n}{k} \end{align*}

Erklärungen zu den Schritten
(1)	Explizite Definition der Binomialkoeffizienten
(2)	Vereinfachen/Zusammenfassen der Nenner
(3)	Gleichnamigmachen der beiden Brüche Erweitern des ersten Bruchs mit \(k\) Erweitern des zweiten Bruchs mit \(n-k\)
(4)	Zusammenfassen von \(k \cdot (k-1)!\) zu \(k!\) gemäß Definition der Fakultät Zusammenfassen von \((n-k) \cdot (n-k-1)!\) zu \((n-k)!\) gemäß Definition der Fakultät
(5)	Zusammenfassen der beiden Brüche zu einem Bruch
(6)	Ausklammern von \((n-1)!\) im Zähler mit dem Distributivgesetz
(7)	Zusammenfassen von \(k+(n-k)\) zu \(n\)
(8)	Zusammenfassen von \((n-1)! \cdot n\) zu \(n!\) gemäß Definition der Fakultät
(9)	Explizite Definition der Binomialkoeffizienten

Beweis der Symmetrie der Binomialkoeffizienten

Die Symmetrie der Binomialkoeffizienten kann durch Nachrechnen gezeigt werden.

\begin{align*} \binom{n}{k} &\overset{(1)}{=} \frac{n!}{(n-k)! \cdot k!} \\[0.75em] &\overset{(2)}{=} \frac{n!}{(n-k)! \cdot \bigl( n-(n-k) \bigr)!} \\[0.75em] &\overset{(3)}{=} \frac{n!}{\bigl(n-(n-k) \bigr)! \cdot (n-k)!} \\[0.75em] &\overset{(4)}{=} \binom{n}{n-k} \end{align*}

Erklärungen zu den Schritten
(1)	Explizite Definition der Binomialkoeffizienten
(2)	Ersetzen von \(k!\) durch das gleichwertige \((n-(n-k))!\)
(3)	Vertauschen der Faktoren im Nenner unter Verwendung des Kommutativgesetzes
(4)	Explizite Definition der Binomialkoeffizienten

Alternativ kann die Symmetrie der Binomialkoeffizienten argumentativ begründet werden: Anstatt aus einer \(n\)-elementigen Menge die \(k\) zu verwendenden Elemente auszuwählen und die restlichen \(n-k\) Elemente zu verwerfen, können aus der \(n\)-elementigen Menge auch die \(n-k\) zu verwerfenden Elemente ausgewählt und die verbleibenden \(k\) Elemente verwendet werden.

Verallgemeinerung

Die Definition der Binomialkoeffizienten kann auf beliebige komplexe Zahlen \(\alpha\) und beliebige ganze Zahlen \(k\) erweitert werden. Für positive ganzzahlige Werte \(k \gt 0\) gilt für den allgemeinen Binomialkoeffizienten:

\begin{align*} \binom{\alpha}{k} &= \frac{\alpha \cdot \bigl( \alpha-1 \bigr) \cdot \ldots \cdot \bigl( \alpha - (k-1) \bigr)}{k!} \\[0.75em] &= \prod\limits_{\ell=1}^{k}{\frac{n+1-\ell}{\ell}} \end{align*}

Für beliebige ganzzahlige Werte \(k\) gilt für den allgemeinen Binomialkoeffizienten entsprechend:

\binom{\alpha}{k} = \begin{cases} \displaystyle\frac{\alpha \cdot \bigl( \alpha-1 \bigr) \cdot \ldots \cdot \bigl( \alpha - (k-1) \bigr)}{k!} & \text{für } k \gt 0, \\[0.75em] 1 & \text{für } k = 0, \\[0.75em] 0 & \text{für } k \lt 0. \end{cases}