Kombinatorik

Was ist Kombinatorik?

Die Kombinatorik ist ein Teilgebiet der Mathematik und wird manchmal der Statistik zugeordnet. In der Kombinatorik beschäftigt man sich mit möglichen Anordnungen von Objekten. Genauer beschäftigt man sich damit, wie viele Anordnungen möglich sind.

Anordnungen, die sich auf alle Elemente einer Menge beziehen, werden auch Permutationen genannt. Bei Permutationen findet keine Auswahl statt. Anordnungen, bei denen eine Auswahl getroffen wird, lassen sich nochmals in Variationen und Kombinationen aufteilen.

Wo benötigt man solche Anzahlen?

Beispielsweise zur Berechnung von Wahrscheinlichkeiten eines Laplace-Experimentes. Diese lassen sich mit dieser Formel berechnen:

$P(E)=\dfrac{|E|}{|\Omega|}=\dfrac{\text{Anzahl aller f}\ddot{\text{u}}\text{r }E \text{ g}\ddot{\text{u}}\text{nstigen Ergebnisse}}{\text{Anzahl aller m}\ddot{\text{o}}\text{glichen Ergebnisse}}$

Wie du siehst, musst du in diesem Zusammenhang Anzahlen bestimmen können.

Permutationen

Die Anzahl der möglichen Permutationen hängt davon ab, ob diese mit oder ohne Wiederholung betrachtet werden.

Permutationen ohne Wiederholung

Schau dir das folgende Beispiel an, um Permutationen besser zu verstehen: Du möchtest an deinem Geburtstag ein Foto von deinen Freunden machen. Wie viele Möglichkeiten gibt es, deine Freunde in einer Reihe aufzustellen? Wenn ihr zum Beispiel $6$ Personen seid, gibt es $6$ Möglichkeiten die erste Person auszuwählen. Für die zweite Person gibt es noch $5$ Möglichkeiten. Für die dritte Person gibt es noch $4$ Möglichkeiten usw. Insgesamt erhältst du $6\cdot 5\cdot 4\cdot 3\cdot 2\cdot1=720$ Möglichkeiten. Eine Kurzschreibweise dafür ist die sogenannte Fakultät. Du schreibst $6! = 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot1=720$. Dies ist eine Permutation ohne Wiederholung.

Permutationen mit Wiederholung

Bei dem obigen Beispiel sind alle Personen unterscheidbar. Wenn von den $n$ Elementen einer Menge $k$ Elemente nicht unterscheidbar sind, dann reduziert sich die Zahl der Anordnungsmöglichkeiten. Die Formel lautet dann $N=\frac{n!}{k!}$.

Im Folgenden betrachten wir Anordnungen, bei denen eine Auswahl von $k$ Elementen aus einer Gesamtheit von $n$ Elementen getroffen wird.

Variationen

Eine Variation ist eine geordnete Stichprobe. Die Reihenfolge der Elemente spielt also eine Rolle. Auch bei Variationen unterscheiden wir zwischen Variationen mit und ohne Wiederholung.

Variationen ohne Wiederholung

Du hast eine Urne, in der sich $n=5$ unterscheidbare Kugeln befinden. Du ziehst dreimal ohne Wiederholung $(k=3)$. Das bedeutet, dass du bei dem ersten Ziehen $5$, beim zweiten $4$ und beim dritten $3$ Möglichkeiten hast. Insgesamt erhältst du $N=5\cdot 4\cdot 3=60$ Möglichkeiten.

Allgemein gilt die Formel $N=\frac{n!}{(n-k)!}$.

Variationen mit Wiederholung

Wir schauen uns das Beispiel mit der Urne und den $n=5$ unterscheidbaren Kugeln nochmals an. Dieses Mal ziehst du mit Wiederholung. Du ziehst die erste Kugel und hast $5$ Möglichkeiten. Dann wiederholst du die Ziehung und hast wieder $5$ Möglichkeiten. Auch beim dritten Versuch hast du $5$ Möglichkeiten. Insgesamt ergeben sich so $5^{3}=125$ Möglichkeiten.

Allgemein gilt $N=n^{k}$.

Wie schon gesagt wird bei all diesen Beispielen die Reihenfolge des Ziehens berücksichtigt. Du unterscheidest also auch noch zwischen Ziehen mit und ohne Berücksichtigung der Reihenfolge.

Kombinationen

Bei einer Kombination handelt es sich um eine ungeordnete Stichprobe. Die Reihenfolge der Objekte wird nicht berücksichtigt. Wir unterscheiden wieder zwischen Kombinationen ohne und mit Wiederholung.

Kombinationen ohne Wiederholung

Ein schönes Beispiel hierfür ist die samstägliche Ziehung der Lottozahlen. Es wird eine Auswahl von $k=6$ aus $n=49$ Kugeln getroffen.

Da die Reihenfolge, in der die Kugeln gezogen werden, keine Rolle spielt, handelt es sich um Kombinationen. Die Anzahl der Variationen lässt sich schnell bestimmen. Es gibt $\frac{49!}{43!}$ mögliche Variationen. Diese Variationen lassen sich nun in Gruppen aufteilen, bei denen dieselben Zahlen vorkommen. Beispielsweise sind die Ziehungen $\{1,22,35,44,27,15\}$ und $\{22,1,35,44,27,15\}$ dieselbe Kombination. Insgesamt gibt es zu jeder Auswahl an Zahlen $6!$ Permutationen. Deshalb erhältst du insgesamt:

$N=\frac{49!}{43!\cdot 6!}=13983816$ bzw. $N = \begin{pmatrix} 49 \\ 6 \end{pmatrix}$

Allgemein erhältst du:

$N=\begin{pmatrix} n \\ k \end{pmatrix}=\frac{n!}{(n-k)!\cdot k!}$

Der Ausdruck $\begin{pmatrix} n \\ k \end{pmatrix}$ heißt Binomialkoeffizient. Du liest ihn als „$n$ über $k$“.

Kombinationen mit Wiederholung

Bei dieser Auswahl stellst du nach jedem „Zug“ wieder die Ausgangssituation her. Die Formel lautet hier:

$N=\begin{pmatrix} n+k-1 \\ k \end{pmatrix}$