Oft kann man den Binomialkoeffizienten $\binom nk$ ohne Taschenrechner im Kopf berechnen. Wir erklären noch einmal, was der Binomialkoeffizient ist und zeigen dann, wie man ihn elegant berechnen kann.
Inhaltsverzeichnis
Was ist der Binomialkoeffizient?
Der Binomialkoeffizient $\binom nk$ berechnet in der Kombinatorik die Anzahl der Möglichkeiten, aus $n$ Dingen $k$ auszuwählen – ohne Wiederholung und ohne Berücksichtigung der Reihenfolge. Beispiel: Wie viele Möglichkeiten gibt es, aus 24 Schülern zwei auszuwählen, die diese Woche Tafeldienst haben?
Die Formel zur Berechnung von $\binom nk$ ist:
$$\binom nk=\frac{n!}{(n-k)!\cdot k!}$$
Dabei ist $n!$ die Fakultät von $n$, also das Produkt der ersten $n$ natürlichen Zahlen. Ein Beispiel:
$$\binom{12}8=\frac{12!}{8!\cdot 4!}=495$$
Man kann in dem Bruch eines Binomialkoeffizienten viel kürzen, und wenn man es tut, hat man oft die Chance, ihn im Kopf zu berechnen. Das obige Beispiel werden wir es am Ende dieses Beitrags ohne Taschenrechner lösen können. Kürzt man nicht, sieht man sich zum Beispiel mit der Zahl
$$12!=479.001.600$$
konfrontiert. Wir sehen, Fakultäten werden sehr schnell sehr groß.
Warum das Ganze, wenn der Taschenrechner doch eine Funktion nCr hat, die den Binomialkoeffizienten bestimmt? Nun, ich finde, es verbessert die Einsicht in das Thema, wenn man ein bißchen mit dem Ausdruck umgehen kann. Und gerade Terme wie $\binom n0$ und $\binom n1$ muss man auch ohne Taschenrechner schnell vereinfachen können.
Der Binomialkoeffizient $\binom n1$
Wie viele Möglichkeiten gibt es, aus 24 Schülern einen auszuwählen, der heute Tafeldienst hat? Natürlich genau 24. Der entsprechende Binomialkoeffizient bestätigt das:
$$\binom{24}{1}=\frac{24!}{23!\cdot 1!}=\frac{24!}{23!}=24$$
Im letzten Schritt haben wir sämtliche Faktoren von $23!$ gekürzt, und es bleibt nur der Faktor 24 im Zähler übrig.
Dahinter steckt folgende Regel: Für alle natürlichen Zahlen $n\in\mathbb N$ ist $\displaystyle\binom n1=n$.
Der Binomialkoeffizient $\binom nn$
Wie viele Möglichkeiten gibt es, aus $n$ Dingen $n$ auszuwählen? Genau eine, nämlich die Auswahl von allen Elementen. Die Reihenfolge spielt ja keine Rolle. Wir rechnen es nach:
$$\binom nn=\frac{n!}{0!\cdot n!}=\frac{n!}{n!}=1$$
Beachte, dass $0!=1$ ist.
Der Binomialkoeffizient $\binom n0$
Wie viele Möglichkeiten gibt es, aus $n$ Dingen $0$ auszuwählen? Wenn du jetzt sagst: „Keine!“ – dann stimmt das nicht. Es gibt eine Möglichkeit, nämlich indem man keines auswählt. Wir rechnen nach:
$$\binom n0=\frac{n!}{(n-0)!\cdot 0!}=\frac{n!}{n!}=1$$
Der Binomialkoeffizient $\binom n2$
Auch der Binomialkoeffizient $\binom n2$ lässt sich recht einfach berechnen:
$$\binom n2=\frac{n!}{(n-2)!\cdot 2!}=\frac{n\cdot(n-1)}2$$
Damit können wir die Tafeldienst-Frage vom Anfang beantworten: Wie viele Möglichkeiten gibt es, aus 24 Schülern 2 auszuwählen, die diese Woche Tafeldienst haben? Die Antwort:
$$\binom{24}2=\frac{24\cdot 23}2=12\cdot 23=276$$
Dieser Term berechnet auch die Anzahl der Spiele in der Fußball-Bundesliga: Wie viele Spiele gibt es, wenn alle 18 Mannschaften der Bundesliga gegen alle anderen Mannschaften antreten?
$$\binom{18}2=\frac{18\cdot 17}2=9\cdot 17=153$$
Und wenn es Hin- und Rückspiel gibt, dann sind es $2\cdot 153=306$ Spiele. So viele Spiele werden gebraucht, um den Deutschen Fußballmeister zu bestimmen.
Symmetrie des Binomialkoeffizienten
Für jeden Binomialkoeffizienten gilt die folgende einfache Regel:
$$\binom nk=\binom n{n-k}$$
Das können wir uns anschaulich klarmachen: Anstatt aus $n$ Dingen $k$ auszuwählen, kann man auch die $n-k$ Dinge festlegen, die man nicht auswählt. Für den Binomialkoeffizienten $\binom{12}8$ bedeutet das:
$$\binom{12}8=\binom{12}4$$
Zum mathematischen Beweis dieser Regel berechnen wir $\binom n{n-k}$:
$$\binom n{n-k}=\frac{n!}{n-(n-k)!\cdot (n-k)!}=\frac{n!}{k!\cdot(n-k)!}=\binom nk$$
Im Nenner vertauschen sich also einfach die Faktoren.
Eine wichtige Rechenhilfe
Zur Berechnung von $\binom nk$ ohne Taschenrechner gibt es folgende hilfreiche Regel: Im Zähler stehen k Faktoren ”von oben“, im Nenner k Faktoren ”von unten“. Das sieht dann so aus:
$$\binom 83=\frac{8\cdot 7\cdot 6}{1\cdot 2\cdot 3}=8\cdot 7=56$$
Diese Regel kürzt schon einiges heraus, und den Rest kürzt man von Hand. In Kombination mit der vorigen Regel können wir nun elegant den Binomialkoeffizienten $\binom{12}8$ berechnen:
$$\binom{12}8=\binom{12}4=\frac{12\cdot 11\cdot 10\cdot 9}{1\cdot 2\cdot 3\cdot 4}=11\cdot 5\cdot 9=495$$
Mächtigkeit von Teilmengen
Die „Anzahl der Möglichkeiten, aus n Dingen k auszuwählen“ können wir auch etwas mathematischer formulieren, nämlich mit Hilfe von Mengen. Wenn eine Menge $M$ genau $n$ Elemente enthält, nennen wir diese Zahl die Mächtigkeit von $M$, und wir schreiben:
$$|M|=n$$
Der Binomialkoeffizient $\binom nk$ bestimmt dann, wie viele $k$-elementige Teilmengen $M$ besitzt.
Das macht vielleicht etwas deutlicher, warum $\binom n0=1$ ist. Denn die eine 0-elementige Teilmenge von $M$ ist die leere Menge.
Beispiele: Anwendungen von $\binom nk$
Zum Abschluss listen wir einige Anwendungen auf, bei denen der Binomialkoeffizient die Antwort liefert:
- Anzahl der 3-elementigen Teilmengen einer 5-elementigen Menge: $\binom 53$
- Anzahl der möglichen Lottoziehungen beim Lotto „6 aus 49“: $\binom{49}6$
- Anzahl der Möglichkeiten, aus 24 Schülern 3 für einen Ausschuss auszuwählen, der den Schulausflug vorbereitet: $\binom{24}{3}$
- Aus 18 Spielern wird eine Startelf ausgewählt: $\binom{18}{11}$
- Anzahl der Händedrücke, wenn sich 8 Personen begrüßen? Aus 8 Personen werden 2 ausgewählt, die sich die Hand geben: $\binom 82$
- Anzahl der Möglichkeiten, bei einer Bernoullikette mit $n$ Versuchen genau $k$ Treffer zu erzielen: $\binom nk$