Die Kombinatorik ist ein Teilgebiet der Stochastik, das sich mit dem Abzählen von Möglichkeiten befasst, Zahlen oder allgemeiner Elemente von Mengen auszuwählen und anzuordnen. Dies ist vor allem dann nützlich, wenn man bei einem Laplace-Experiment Wahrscheinlichkeiten nach dem Prinzip „günstige Fälle durch alle Fälle“ berechnen möchte. Das klassische Beispiel ist eine Lotterie: Man muss herausfinden, wie viele Ausgänge der Lotterie einen Gewinn versprechen und wie viele Ausgänge es insgesamt gibt. Dabei müssen die beiden folgenden Fragen beachtet bzw. geklärt werden:
- Kommt es auf die Reihenfolge der Zahlen/Elemente an?
- Dürfen Zahlen/Elemente mehrfach auftreten bzw. sind Wiederholungen erlaubt?
- Werden nur Anordnungen aller n Zahlen/Elemente betrachtet oder auch weniger (z. B. k Zahlen/Elemente mit k < n).
Man hat es dann mit Permutationen (Anordnungen aller Elemente mit/ohne Wiederholungen unter Berücksichtigung der Reihenfolge), Variationen (Auswahl einiger Elemente mit/ohne Wiederholungen unter Berücksichtigung der Reihenfolge) und Kombinationen (Auswahl einiger Elemente mit/ohne Wiederholungen ohne Beachtung der Reihenfolge) der Zahlen/Elemente zu tun.
Sehr hilfreich bei der Untersuchung von kombinatorischen Problemen sind Urnenmodelle. Bei Urnenmodellen sagt man statt „mit/ohne Wiederholungen“ meist „mit/ohne Zurücklegen“.
Beispiele:
Wir betrachten die Menge A der ersten fünf Buchstaben {a, b, c, e, d}, es treten also keine Wiederholungen auf bzw. alle Elemente sind verschieden und unterscheidbar.
- Permutationen ohne Wiederholungen dieser Menge sind z. B. die Anordnungen (c, a, e, d, b) und (c, a, b, d, e). Es gibt insgesamt 5! = 120 (siehe Fakultät) verschiedene Permutationen von 5 Elementen, wenn keine Wiederholungen erlaubt sind.
- Eine Variation der Menge A ohne Wiederholungen ist eine geordnete Stichprobe vom Umfang k, bei der alle Elemente verschieden sein sollen, also z. B. für k = 3 (a, e, b) oder (c, a, b). Es gibt \(\displaystyle \frac{5!}{(5-3)!} = \displaystyle \frac{5!}{2!} =5 \cdot 4 \cdot 3 = 60\) 3er-Variationen von 5 Elementen, wenn keine Wiederholungen erlaubt sind.
- Eine Kombination der Menge A ohne Wiederholungen ist eine ungeordnete Stichprobe vom Umfang k mit verschiedenen Elementen, also einfach eine Teilmenge mit k Elementen. Deren Zahl entspricht der Zahl der Variationen geteilt durch die Zahl der Anordnungen bzw. Permutationen der k Elemente. Für k = 3 hat man also z. B. die Kombinationen {a, b, e} oder {c, d, e}. Die Zahl der 3er-Kombinationen von 5 Elementen, beträgt, wenn keine Wiederholungen erlaubt sind, \(\displaystyle \frac{5!}{(5-3)!\cdot3!} = \begin{pmatrix}5\\3\end{pmatrix} = 10\) (der mittlere Ausdruck ist ein Binomialkoeffizient).
Wir betrachten jetzt den Fall, dass Wiederholungen erlaubt sein sollen.
- Bei der Menge B = {a, b, b, b, d} tritt das „b“ dreimal auf. Es gibt jetzt weniger Permutationen als im Fall ohne Wiederholungen, da Vertauschungen der drei „b“ untereinander zur selben Anordnung führen würden. Die Zahl der Permutationen von B (Wiederholungen erlaubt) ist also gleich der Zahl der Permutationen ohne Wiederholungen geteilt durch die Zahl der Permutationen der drei ununterscheidbaren „b“. Dies ergibt \(\displaystyle \frac{5!}{3!} = 5 \cdot4 = 20\) Permutationen von fünf Elementen, wenn eines dreimal wiederholt ist.
Im Fall der Menge C = {a, a, b, b, b}, in der ein Element zweimal und eines dreimal wiederholt wird, sind es entsprechend \(\displaystyle \frac{5!}{2! \cdot 3!} = 10\) Permutationen. - Eine Variation der Menge A mit Wiederholungen ist eine geordnete Stichprobe vom Umfang k, bei der einzelne Elemente mehrfach auftreten dürfen (aber nicht müssen!), also z. B. für k = 3 (a, e, a) oder (c, c, b). Es gibt 53 = 125 verschiedene 3er-Variationen von 5 Elementen, wenn Wiederholungen erlaubt sind.
- Eine Kombination der Menge A mit Wiederholungen ist eine beliebige ungeordnete Stichprobe vom Umfang k oder einfacher ausgedrückt eine Menge von k gleichen oder verschiedenen Elementen von A. Für k = 3 wären das z. B. {a, a, a} oder {c, d, e}. Die Formel für die Zahl der 3er-Kombinationen von 5 Elementen lautet, wenn Wiederholungen erlaubt sind, \(\displaystyle \frac{(5 + 3 - 1)!}{(5-1)!\cdot3!} = \begin{pmatrix}5 + 3 - 1\\3\end{pmatrix} = 35\).
Den Unterschied zwischen Permutationen/Variationen einerseits und Kombinationen andererseits kann man auch dadurch verdeutlichen, dass Permutationen und Variationen als Tupel, Kombinationen dagegen als Mengen aufgelistet werden.
Allgemein formuliert:
| keine Wiederholungen | Wiederholungen erlaubt | |
|---|---|---|
| Permutationen (Anordnungen, Tupel) | Man kann n verschiedene Elemente auf n! unterschiedliche Weisen anordnen. | Wenn von n Elementen jeweils k1, k2, … untereinander gleich sind, kann man sie auf \(\displaystyle \frac{n!}{k_1! \cdot k_2! \cdot \ldots}\) verschiedene Weisen anordnen. |
| Variationen (geordnete Stichproben, Tupel) | Es gibt \(\displaystyle \frac{n!}{(n-k)!}\) Möglichkeiten, aus einer Menge von n Elementen k unterschiedliche Elemente anzuordnen. | Es gibt nk Möglichkeiten, aus einer Menge von n Elementen k beliebige Elemente anzuordnen. |
| Kombinationen (Auswahlen, Mengen) |
Die Zahl der k-elementigen Teilmengen einer Menge aus n Elementen beträgt \(\displaystyle \frac{n!}{(n-k)!\cdot k!} = \begin{pmatrix}n\\k\end{pmatrix}\). Dies ist gleichzeitig die Zahl der Möglichkeiten, von n unterschiedlichen Elementen k verschiedene auszuwählen. |
Man kann auf \(\displaystyle \frac{(n+k-1)!}{(n-1)!\cdot k!} = \begin{pmatrix}n+k-1\\k\end{pmatrix}\) verschiedene Weisen k beliebige Elemente aus einer Menge von n Elementen auswählen. |