Inhalt
» Vorbemerkung
» Faktorielle und Binominialkoeffizient
» Die Formeln
» Beispiele

Vorbemerkung

Die Kombinatorik zählt die Anzahl der Möglichkeiten bei Versuchsausgängen. In der Schule unterscheiden wir dabei meist nur, ob uns die Reihenfolge der eingetretenen Ergebnisse interessiert und ob sich ein Ergebnis wiederholen kann oder nicht. Oft werdet ihr die Begriffe Kombination und Permutation lesen.

Oft stellt man sich das ganze Experiment als sogenanntes Urnenmodell vor. Die Kugeln sind mit unseren möglichen Ergebnisse beschriftet und wir überlegen ob wir diese mit oder ohne Wiederholung (m.W., o.W.) beziehungsweise mit oder ohne Beachtung der Reihenfolge (m.R., o.R.) ziehen.

Lotto ist ein Experiment ohne Beachtung der Reihenfolge der gezogenen Kugeln und ohne Zurücklegen. Bei einem Zahlenschloss an einem Fahrrad ist sowohl die Reihenfolge, als auch das wiederholte Auftreten der Ziffern möglich. Die Bücher in einem Regal werden in einer bestimmten Reihenfolge archiviert aber wir besitzen üblicherweise die Bücher nur ein mal (o.W.). Die Auswahl von fünf Volleyball-Spielerinnen aus einem Kader von 15 Spielerinnen findet ohne Wiederholung und ohne Beachtung der Reihenfolge (ignorieren wir Positionen) statt. Die Startreihung bei einem 400m Lauf findet ohne Wiederholung und mit Beachtung der Reihenfolge (Innen- oder Außenbahn) statt. Wir sehen also, dass wir viele Aufgaben des Alltags nach diesem Muster einteilen können.

Faktorielle und Binominialkoeffizient

Wir benötigen zum kürzeren Aufschreiben unserer Überlegungen zwei neue Rechenoperationen. Wir benötigen die sogenannten Faktorielle, dargestellt durch ein Ausrufezeichen !, und definieren

\begin{align*}
n!:=n\cdot (n-1)\cdot (n-2)\cdot \ldots \cdot 3\cdot 2\cdot 1.
\end{align*}

Damit können wir dann den sogenannten Binominialkoeffizient \(\binom{n}{k}\) definieren. Wir lesen ihn "\(n\) über \(k\)" oder manchmal auch "\(k\) aus \(n\)" und rechnerisch erhalten wir

\begin{align*}
\binom{n}{k}=\frac{n!}{k!\cdot (n-k)!}
\end{align*}

Es ist wichtig zu wissen, dass \(0!:=1\) gilt. Genauso hilfreich ist einfach nachprüfbare Tatsache, dass gilt

\begin{align*}
\binom{n}{0}=\binom{n}{n}=1.
\end{align*}

Die Formeln

Wie zuvor geschrieben unterscheiden wir nach diesen zwei Kriterien (Wiederholung W und Reihenfolge R) und erhalten damit \(2\cdot 2=4\) Formeln (das war gerade unsere erste kombinatorische Berechnung). Wir denken in Urnen, also überlegen wir, wie viele Kugeln in der Urne liegen (\(n\)), und wie oft wir ziehen (\(k\)). Dann erhalten wir folgende Übersicht:

  m. W. o. W.
m. R. \(n^k\) \(\frac{n!}{(n-k)!}\)
o. R. \(\binom{n+k-1}{k}\) \(\binom{n}{k}\)
Beispiele

Zahlenschlösser: Ein Zahlenschloss besitzt die Ziffern 0 bis 9 und hat üblicherweise drei oder vier Rädchen. Wie viele Möglichkeiten gibt es für das Passwort?

Lösung

Wir stellen uns eine Urne vor mit den Kugeln 0 bis 9, \(n=10\). Wir ziehen drei beziehungsweise vier mal, \(k_1=3\), \(k_2=4\), bei einem Ziffernschloss ziehen wir mit Wiederholung und mit Beachtung der Reihenfolge. Daher erhalten wir

\(n^k_1=10^3=1000,\qquad n^k_2=10^4=10000\)

Möglichkeiten. Ein vierstelliges Schloss ist also zehn mal so sicher.

Gläserklirren: Bei einem Sektempfang an einer Hochzeit sind einhundert Gäste anwesend. Jeder Gast soll mit jedem anderen Gast anstoßen. Wie oft klirren die Gläser?

Lösung

In unserer Urne liegen einhundert Kugeln und pro Klirren benötigen wir zwei Gäste, also haben wir \(n=100\) und \(k=2\). Niemand stoßt mit sich selbst an, also keine Wiederholung, und die Reihenfolge ist unwichtig, da es beim Anstoßen kein 1. und 2. gibt. Daher erhalten wir:

\begin{align*}
\binom{n}{k}=\binom{100}{2}=4950
\end{align*}

800-m Lauf: In einem 800-m Rennen starten acht Läuferinnen. Wie viele Möglichkeiten gibt es, dass Podest mit den ersten drei Plätzen zu besetzen?

Lösung

Wir haben acht Kugeln, \(n=8\), und wählen drei Personen aus, die ersten drei Plätze, \(k=3\). Die Reihenfolge ist hier natürlich wichtig und logischerweise kann niemand zwei Plätze einnehmen, also ohne Wiederholung und mit Beachtung der Reihenfolge. Daraus folgen

\(\frac{n!}{(n-k)!}=\frac{8!}{5!}=8\cdot 7\cdot 6=336\)

Möglichkeiten.

Die Mississippi-Formel: In diesem Beispiel geht es um Anagramme. Wie viele Wörter kann ich aus "\(s,t,e,f,a,n\)", "\(s,o,n,n,e\)", "\(a, n, n, a\)" beziehungsweise letztendlich "\(m,i,s,s,i,s,s,i,p,p,i\)" bilden?

Lösung

Wir beginnen mit "\(s,t,e,f,a,n\)". Bei Wörtern ist die Reihenfolge wichtig und wir verwenden keine der sechs Buchstaben zwei mal, also o.W. und m.R. Wir haben also sechs "Kugeln" und verwenden alle sechs, daher \(n=k=6\). Eingesetzt in unsere Formel erhalten wir

\(\frac{n!}{(n-k)!}=\frac{6!}{0!}=6!=720.\)

Kommen wir zu "\(s,o,n,n,e\)", wir haben die selben Vorüberlegungen und \(n=k=5\). Es stellt sich jedoch die Frage, haben wir aufgrund der zwei n wirklich analog \(5!\) Wörter? Können wir die Wörter \(sonne\) und \(sonne\), unterscheiden? Genauer gesagt \(son_1 n_2 e\) und \(son_2 n_1 e\)? Nein! Wie viele haben wir zu viel gezählt hängt davon ab, wie viele Möglichkeiten wir erhalten, \(n_1\) und \(n_2\) zu vertauschen (ohne das wir es bemerken), das sind \(2!=2\). Dadurch erhalten wir nur

\begin{align*}
\frac{5!}{2!}=60
\end{align*}

Möglichkeiten. Diese Vorgehensweise nutzen wir nun auch bei "\(a, n, n, a\)" und erhalten

\begin{align*}
\frac{4!}{2!\cdot 2!}=6
\end{align*}

Wörter. Diese können wir sogar aufschreiben, aann, anna, nnaa, anan, nana, naan. Letztendlich ergeben dann die Buchstaben von "\(m,i,s,s,i,s,s,i,p,p,i\)"

\begin{align*}
\frac{11!}{4!\cdot 4! \cdot 2!}=34650
\end{align*}

Wörter und die Mississippi-Regel wird sich gerne an diesem Beispiel gemerkt.