Der Binomialkoeffizient

Aufgabe 1: Definition des Binomialkoeffizienten

Wie ist der Binomialkoeffizient \({n\choose k}\) definiert? Welche Zahlen kann man für n und k einsetzen?

Aufgabe 2: Rechenregeln

Rechne mit Hilfe der Definition nach, dass die folgenden Rechenregeln für Binomialkoeffizienten gelten:

  1. \({n\choose n}=1\)
  2. \({n\choose 0}=1\)
  3. \({n\choose 1}=n\)
  4. \({n\choose 2}=\frac{n\cdot(n-1)}2\)
  5. \({n\choose k}={n\choose n-k}\)
  6. \({n\choose k}=\frac{n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot(n-k+1)}{1\cdot 2\cdot 3\cdot\ldots\cdot k}\)

Regel 6 sieht etwas unübersichtlich aus, ist aber ganz einfach anzuwenden: Wenn man \({n\choose k}\) berechnen will, stehen im Zähler k Faktoren „von oben“ und im Nenner k Faktoren von unten. Ein Beispiel:
$${12\choose 3}=\frac{12\cdot 11\cdot 10}{1\cdot 2\cdot 3}$$
Den Rest erledigt man dann durch Kürzen.

Aufgabe 3: Binomialkoeffizienten berechnen

Berechne mit Hilfe der Regeln aus Aufgabe 2 und ohne Taschenrechner die folgenden Binomialkoeffizienten:

In diesem Text zeigen wir, was der Binomialkoeffizient ist und wie er in der Stochastik benutzt wird. Zunächst erklären wir, was der Binomialkoeffizient ist und wie man ihn berechnet. Wir zeigen einige einfache Rechenregeln, mit denen man ihn schnell ohne Taschenrechner bestimmen kann. Anschließend geht es darum, wofür er eigentlich benötigt wird: nämlich um die Anzahl von Teilmengen einer Menge zu bestimmen. Dann zeigen wir auch, wie man den Binomialkoeffizienten mit einem Pascalschen Dreieck bestimmen kann und was er mit den binomischen Formeln zu tun hat.

Berechnung des Binomialkoeffizienten

Der Binomialkoeffizient \({n\choose k}\) (sprich: „n über k“) wird mit folgender Formel berechnet:
$${n\choose k}=\frac{n!}{(n-k)!\cdot k!}$$
Für n und k können wir alle natürlichen Zahlen und die 0 einsetzen. Es soll aber k nicht größer als n sein, da \(n-k\) sonst negativ wird, und negative Zahlen haben keine Fakultät.

Als Beispiel rechnen wir für \(n=5\) alle Binomialkoeffizienten aus, die es gibt:
$$\require{cancel}\begin{eqnarray*}{5\choose 0} & = & \frac{5!}{(5)!\cdot 0!}=\frac{\cancel{5!}}{\cancel{5!}\cdot 1}=1\\
{5\choose 1} & = & \frac{5!}{4!\cdot 1!}=5\\
{5\choose 2} & = & \frac{5!}{3!\cdot 2!}=\frac{5\cdot 4\cdot\cancel 3\cdot\cancel 2\cdot\cancel 1}{\cancel 3\cdot \cancel 2\cdot\cancel 1\cdot 2\cdot 1}=\frac{5\cdot 4}{2\cdot 1}=10\\
{5\choose 3} & = & \frac{5!}{2!\cdot 3!}=\frac{5\cdot 4\cdot\cancel 3\cdot\cancel 2\cdot\cancel 1}{2\cdot 1\cdot \cancel 3\cdot \cancel 2\cdot\cancel 1}=\frac{5\cdot 4}{2\cdot 1}=10\\
{5\choose 4} & = & \frac{5!}{1!\cdot 4!}=\frac{5\cdot\cancel 4\cdot\cancel 3\cdot\cancel 2\cdot\cancel 1}{1\cdot \cancel 4\cancel 3\cdot \cancel 2\cdot\cancel 1}=5
\\{5\choose 5} & = & \frac{\cancel{5!}}{0!\cdot\cancel{5!}}=1\end{eqnarray*}$$

Aus diesen Ergebnissen lassen sich einige Regeln und Rechenhilfen für Binomialkoeffizienten ableiten:

Die Fälle k=0 und k=n

Für alle natürlichen Zahlen n gilt stets:
$${n\choose 0}=1\text{ und }{n\choose n}=1$$

Der Fall k=1

Für alle natürlichen Zahlen n gilt stets:
$${n\choose 1}=n$$

Symmetrische Ergebnisse

In der obigen Liste erkennt man, dass sich die Werte der Binomialkoeffizienten in einer symmetrischen Weise wiederholen und zwar gemäß folgender Regel:
$${n\choose k}={n\choose n-k}$$
Das liegt daran, dass sich für k und n-k im Nenner die Faktoren einfach vertauschen, und lässt sich auch schnell formal nachrechnen:
$${n\choose n-k}=\frac{n!}{(n-(n-k))!\cdot (n-k)!}=\frac{n!}{k!\cdot(n-k)!}={n\choose k}$$

Kürzen

Bei der Berechnung des Binomialkoeffizienten kann man jede Menge kürzen, wie das nächste Beispiel zeigt. Man kann sogar immer alle Faktoren des Nenners kürzen, so dass niemals ein Bruch als Ergebnis herauskommt.
$$\require{cancel}{8\choose 5}=\frac{8!}{3!\cdot 5!}=\frac{\cancel 1\cdot\cancel 2\cdot\cancel 3\cdot\cancel 4\cdot\cancel 5\cdot 6\cdot 7\cdot 8}{1\cdot 2\cdot 3\cdot\cancel 1\cdot\cancel 2\cdot\cancel 3\cdot\cancel 4\cdot\cancel 5}=\frac{\cancel 6\cdot 7\cdot 8}{1\cdot\cancel 2\cdot\cancel 3}=7\cdot 8=56$$
Das Kürzen hilft dabei, dass man Binomialkoeffizienten auch größerer Zahlen oft ohne Taschenrechner berechnen kann.

Merkregel zur Berechnung des Binomialkoeffizienten

Das viele Kürzen führt zu einer Merkregel, die sich einfacher in Worten als mit einer Gleichung formulieren lässt. Trotzdem notieren wir zuerst die Gleichung. Es gilt nämlich:
$${n\choose k}=\frac{n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot(n-k+1)}{1\cdot 2\cdot 3\cdot\ldots\cdot k}$$
Im Zähler stehen k Faktoren von n abwärts, denn die Faktoren 1 bis \(n-k\) wurden gekürzt. Im Nenner stehen nur noch die k Faktoren von k!. Also lautet die Merkregel:
$${n\choose k}=\frac{k\text{ Faktoren von n abwärts}}{k\text{ Faktoren von 1 aufwärts}}$$
Ein Beispiel zur Berechnung:
$$\require{\cancel}{8\choose 3}=\frac{8\cdot 7\cdot\cancel 6}{1\cdot\cancel 2\cdot\cancel 3}=56$$
Wir können die Merkregel auch mit der Symmetrie kombinieren und rechnen:
$${12\choose 9}={12\choose 3}=\frac{12\cdot 11\cdot 10}{1\cdot 2\cdot 3}=6\cdot 11\cdot 10=660$$

Spezialfälle

Wenn man eine neue Formel kennenlernt, probiert man gerne erst einmal besondere Zahlen aus, um sie besser kennenzulernen. Ein besonderer Fall ist, für n und k dieselbe Zahl einzusetzen:
$$\require{cancel}{5\choose 5}=\frac{5!}{(5-5)!\cdot 5!}=\frac{\cancel{5!}}{0!\cdot\cancel{5!}}=1$$

Hier haben wir verwendet, dass \(0!=1\) ist. Ein weiterer Spezialfall ist \(k=0\):
$$\require{cancel}{7\choose 0}=\frac{7!}{(7-0)!\cdot 7!}=\frac{\cancel{7!}}{\cancel{7!}\cdot 0!}=1$$
Einige Rechenregeln für den Binoamialkoeffizienten:

  1. \({n\choose n}=1\)
  2. \({n\choose 0}=1\)
  3. \({n\choose n-k}={n\choose k}\)
  4. \({n\choose k}=\frac{n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot(n-k+1)}{1\cdot 2\cdot 3\cdot\ldots\cdot k}\)

Diese Regeln rechnen wir nun nach und verwenden bei 1. und 2., dass 0!=1 ist.

  1. \({n\choose n}=\frac{n!}{0!\cdot n!}=\frac{n!}{1\cdot n!}=1\)
  2. \({n\choose 0}=\frac{n!}{(n-0)!\cdot 0!}=\frac{n!}{n!\cdot 1}=1\)

Damit können wir wie folgt rechnen:
$${12\choose 9}={12\choose 3}=\frac{12\cdot 11\cdot 10}{1\cdot 2\cdot 3}=2\cdot 11\cdot 10=220$$

Es ist \({n\choose n}=\frac{n!}{0!\cdot n!}=\frac{n!}{1\cdot n!}=1\). Anschaulich gesprochen gibt es genau eine Möglichkeit, aus n Dingen n auszuwählen.

Es ist \({n\choose 0}=\frac{n!}{(n-0)!\cdot 0!}=\frac{n!}{n!\cdot 1}=1\). Anschaulich gesprochen gibt es genau eine Möglichkeit, aus n Dingen 0 auszuwählen, nämlich die leere Menge.

Außerdem gilt \({n\choose k}={n\choose n-k}\), wie man durch Einsetzen in die Definition leicht feststellt. Im Nenner vertauschen sich nämlich genau die Faktoren.

Ein schnelles Rechenbeispiel mit den Zahlen \(n=8\) und \(k=3\):
$${8\choose 3}=\frac{8!}{5!\cdot 3!}=56$$

Die Lösung 56 hat hier der Taschenrechner geliefert. Wir wollen hier aber nicht nur Formeln auswendig lernen und den Taschenrechner bedienen, sondern wir wollen verstehen, wie der Hase läuft. Am Ende dieses Textes wirst du verstehen, warum die Formel so ist wie sie ist. Und du kannst das obige Beispiel und viele weitere ohne Taschenrechner berechnen. Deshalb gehen wir einen Schritt zurück und betrachten folgende Übungsaufgabe:

Aus den 24 Schülern einer Klasse sollen 5 ausgewählt werden, um die nächste Klassenfahrt vorzubereiten. Wie viele Möglichkeiten gibt es, diesen Ausschuss zu besetzen?

In diesem Text wollen wir klären, was der Binomialkoeffizient „n über k“ ist. Wir schreiben zuerst ganz nüchtern die Definition hin und setzen ein paar Zahlen ein. Darüber kommen wir zu Regeln, wie man ihn geschickt ohne Taschenrechner berechnen kann. Und wir besprechen die wichtigste Eigenschaft, dass nämlich \({n\choose k}\) die Anzahl Möglichkeiten angibt, aus n Dingen k auszuwählen. Schließlich erklären wir noch das Pascalsche Dreieck und was dieses mit den binomischen Formeln zu tun hat.

Und wenn du den Text bis zum Ende durchgearbeitet hast, weißt du genug über den Binomialkoeffizienten, um gut durch den Stochastik-Kurs in der Schule zu kommen. Aber genug der Vorrede, wir definieren nun formal, was \({n\choose k}\) sein soll.

Definition des Binomialkoeffizienten

Erinnerung: Die natürlichen Zahlen sind die Menge \(\{1,2,3,4,…\}\), also die positiven ganzen Zahlen. Es seien nun n und k zwei natürliche Zahlen, wobei k nicht größer als n sein soll. Dann definieren wir:
$${n\choose k}=\frac{n!}{(n-k)!\cdot k!}$$
und nennen \({n\choose k}\) den Binomialkoeffizienten „n über k“.

Wir wollen diese Definition sofort mit Leben füllen und rechnen aus, was \({8\choose 3}\) ist:
$${8\choose 3}=\frac{8!}{(8-3)!\cdot 3!}=$$
Dabei soll \(n\ge k\) sein, da sonst der Ausdruck \((n-k)!\) nicht definiert ist.

Beispiele zur Berechnung des Binomialkoeffizienten

Hier kommen einige Rechenbeispiele:

Rechenregel: Binomialkoeffizient im Kopf berechnen

Mit der folgenden Regel kann man den Binomialkoeffizenten häufig ohne Taschenrechner bestimmen:
$${n\choose k}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+1)}{1\cdot 2\cdot\ldots\cdot k}$$

Anschaulich gesprochen sagt die Regel: Im Zähler stehen k Faktoren „von oben“, und im Nenner stehen k Faktoren „von unten“. Beispiel:

$${8\choose 3}=\frac{8\cdot 7\cdot 6}{1\cdot 2\cdot 3}=8\cdot 7=56$$

Man kann die Regeln auch kombinieren:

$${14\choose 12}={14\choose 2}=\frac{14\cdot 13}{1\cdot 2}=7\cdot 13=91$$

Übrigens kann man bei der Berechnung des Binomialkoeffizienten immer alle Faktoren im Nenner wegkürzen. Es kommt also immer eine natürliche Zahl heraus.

Binomialkoeffizient zählt Teilmengen

Der Binomialkoeffizient \({n\choose k}\) bestimmt die Anzahl der Möglichkeiten, aus n Elementen k auszuwählen – ungeordnet und ohne Wiederholung. Etwas mathematischer ausgedrückt: Eine Menge mit n Elementen hat \({n\choose k}\) k-elementige Teilmengen. Warum ist das so?

Dazu eine Beispielaufgabe: Aus den 24 Schülern der Klasse soll ein fünfköpfiger Ausschuss gebildet werden, der die nächsten Klassenfahrt plant. Wie viele Möglichkeiten gibt es, diesen Ausschuss zusammenzustellen?

Wir stellen uns vor, wir wählen die Schüler der Reihe nach aus. Dafür gibt es
$$24\cdot 23\cdot 22\cdot 21\cdot 20 =\frac{24!}{19!}$$
Möglichkeiten. Dann hätten wir aber die Schüler geordnet ausgewählt und jede Teilmenge vielfach gezählt. Die Auswahl ABCDE soll aber die gleiche sein wie CAEDB. Da man die fünf ausgewählten Schüler auf 5! Arten anordnen kann, müssen wir obiges Ergebnis noch durch 5! teilen und erhalten als Endergebnis:
$$\frac{24!}{19!\cdot 5!}=\frac{24!}{(24-5)!\cdot 5!}={24\choose 5}$$

Zusammenfassend können wir sagen, dass in dem Binomialkoeffizienten
$${n\choose k}=\frac{n!}{(n-k)!\cdot k!}$$
die Fakultäten folgende Bewandtnis haben:

  • n! gibt die Anzahl Möglichkeiten an, alle n Elemente geordnet auszuwählen.
  • k! gibt die Anzahl Möglichkeiten an, die k ausgewählten Elemente untereinander zu vertauschen.
  • (n-k)! gibt die Anzahl Möglichkeiten an, die übrigen n-k Elemente untereinander zu vertauschen.

Insgesamt liefert \({n\choose k}\) die Anzahl Möglichkeiten, aus n Dingen k ungeordnet auszuwählen, und damit die Anzahl k-elementiger Teilmengen einer n-elementigen Menge.

Anzahl Teilmengen gesamt

Wie viele Teilmengen hat eine n-elementige Menge insgesamt? Wenn wir eine Teilmenge zusammenstellen, gehört jedes Element dazu oder nicht – das sind n Entscheidungen mit jeweils zwei Möglichkeiten. Also gibt es insgesamt
$$\underbrace{2\cdot 2\cdot\ldots\cdot 2}_n=2^n$$
Teilmengen einer n-elementigen Menge. Die Anzahl k-elementiger Teilmengen haben wir oben schon als \({n\choose k}\) bestimmt, und da jede Teilmenge zwischen 0 und n Elemente besitzt, haben wir folgende Gleichung hergeleitet:
$${n\choose 0}+{n\choose 1}+{n\choose 2}\ldots+{n\choose n}=2^n$$
Beispiel für n = 3:
$${3\choose 0}+{3\choose 1}+{3\choose 2}+{3\choose 3}=8$$

Pascalsches Dreieck

Wenn wir die Binomialkoeffizienten nach dem folgenden Schema als Dreieck anordnen, stellen wir fest, dass jede Zahl in dem Schema gleich der Summe der beiden Zahlen darüber ist:

$$\begin{array}{c}
{0\choose 0}
\\
{1\choose 0} {1\choose 1}
\\
{2\choose 0} {2\choose 1} {2\choose 2}
\\
{3\choose 0} {3\choose 1} {3\choose 2} {3\choose 3}
\\
{4\choose 0} {4\choose 1} {4\choose 2} {4\choose 3} {4\choose 4}
\end{array}$$

$$\begin{array}{c}
{1}\qquad
\\
{1}\qquad {1}\qquad
\\
{1}\qquad {2}\qquad {1}\qquad
\\
{1}\qquad {3}\qquad {3}\qquad {1}\qquad
\\
{1}\qquad {4}\qquad {6}\qquad {4}\qquad {1}\qquad
\end{array}$$

Das Pascalsche Dreieck stellt also eine Möglichkeit dar, Binomialkoeffizienten schnell zu bestimmen. Es gelten folgende Regeln:

  • In Zeile n des Dreiecks steht in Spalte k der Wert \({n\choose k}\), also die Anzahl aller k-elementigen Teilmengen einer n-elementigen Menge. Dabei beginnt die Nummerierung von Zeilen und Spalten bei 0.
  • Die Zeilensumme der n-ten Zeile ist \(2^n\).
  • Die Zahl an jeder Position des Dreiecks ist die Summe der beiden Zahlen darüber. Diese Regel lässt sich wie folgt als Formel beschreiben:
    $${n\choose k}+{n\choose k+1}={n+1\choose k+1}$$

Pascalsches Dreieck und binomische Formeln

Eine weitere Anwendung erfährt das Pascalsche Dreieck bei den binomischen Formeln. Schauen wir uns einmal die Zeile 2 (die Zählung beginnt bei 0!) des Pascalschen Dreiecks mit den Einträgen 1,2,1 an. Diese Zahlen entsprechen den Koeffizienten der ersten binomischen Formel. Koeffizient ist übrigens der Fachbegriff für die Faktoren vor den Variablen, in der binomischen Formel fettgedruckt dargestellt:
$$(a+b)^2=\mathbf 1a^2+\mathbf 2ab+\mathbf 1b^2$$

Die binomische Formel gibt es auch für höhere Potenzen. In der dritten Potenz sieht sie wie folgt aus, wobei wieder die Koeffizienzen fettgedruckt sind:
$$(a+b)^3=\mathbf 1a^3+\mathbf 3a^2b+\mathbf 3ab^2+\mathbf 1b^3$$
Hier stammen die Koeffizienten aus der dritten Zeile des Pascalschen Dreiecks und sind demzufolge die Binomialkoeffizienten
$${3\choose 0}, {3\choose 1}, {3\choose 2}, {3\choose 3}\text.$$

Diese Regel gibt es auch für alle höheren Potenzen und trägt den Namen „Binomischer Lehrsatz„. Die Koeffizienten stammen dabei aus der n-ten Zeile des Pascalschen Dreiecks:
$$(a+b)^n={n\choose 0}a^nb^0+{n\choose 1}a^{n-1}b^1+{n\choose 2}a^{n-2}b^2+\ldots+{n\choose n-1}a^1b^{n-1}+{n\choose n}a^0b^n$$

Und damit können wir nun auch erklären, warum die Binomialkoeffizienten \(n\choose k\) diesen Namen tragen: weil sie die Koeffizienten im binomischen Lehrsatz darstellen! Und das ist doch ein wunderbarer Abschluss dieses Textes.