Kombinatorik

Teilgebiet der Mathematik, das sich ausschließlich mit endlichen Mengen beschäftigt, insbesondere mit Fragen nach den verschiedenen Möglichkeiten der Auswahl und der Anordnung der Elemente einer solchen Menge. Viele Aufgaben der Kombinatorik fragen nach der Anzahl der Möglichkeiten, eine Auswahl von k Elementen aus einer n-elementigen Teilmenge unter verschiedenen Bedingungen zu treffen, je nachdem ob die Reihenfolge der k Elemente eine Rolle spielt, oder ob Wiederholungen in der Auswahl zugelassen sind. Beispiele für kombinatorische Fragen sind:

a) Wie viele mögliche Lottotipps gibt es, also wie viele Möglichkeiten, 6 Zahlen aus 49 zu ziehen?

b) Wie viele Möglichkeiten gibt es bei einem Pferderennen mit 8 Pferden, die Plätze 1 bis 3 zu belegen?

c) Wie viele vierstellige Zahlen gibt es, die nur die Ziffern 1 und 2 enthalten?

d) Wie viele Würfe mit 2 verschiedenen Würfeln gibt es?

Diese Grundfragen der Kombinatorik korrespondieren zu so genannten Urnenmodellen, in denen man aus einer Urne mit n Kugeln eine Stichprobe von k Kugeln mit oder ohne Zurücklegen der Kugeln zieht und nun nach verschiedenen Möglichkeiten fragt:

1. Wie viele geordnete Stichproben (mit Berücksichtigung der Reihenfolge) gibt es beim Ziehen mit Zurücklegen (Beispiel c)? Antwort: n^k.

2. Wie viele geordnete Stichproben ohne Zurücklegen gibt es (Beispiel b)? Antwort:

(n! ist die Fakultät der Zahl n).

3. Wie viele ungeordnete Stichproben mit Zurücklegen gibt es (Beispiel d)? Antwort:

ist der Binomialkoeffizent n über k.

4. Wie viele ungeordnete Stichproben ohne Zurücklegen gibt es (Beispiel a)? Antwort:

.

Mit der Lösung dieser Probleme stellt die Kombinatorik eine grundlegende Voraussetzung für die Wahrscheinlichkeitsrechnung dar, da die Wahrscheinlichkeit eines bestimmten Ereignisses immer von der Anzahl aller Möglichkeiten abhängt. Weitere wichtige Teilbereiche der Kombinatorik sind die Graphentheorie und die Kodierungstheorie.