Die Probleme der abzählenden Kombinatorik kommen aus ganz verschiedenen Anwendungsgebieten. Es hat sich bewährt, diese Anwendungen in ein Modell zu übersetzen. In diesem Modell gibt es keine Schüler, keine Klassensprecher und keine Läufer, sondern es gibt ein Kugeln in einer Urne. Das ist einfach ein Topf, und für jeden Schüler (oder worum es gerade geht) ist eine Kugel in diesem Topf. Wenn die Dinge unterscheidbar sein sollen, können die Kugeln mit Zahlen beschriftet sein, oder es können verschiedenfarbige Kugeln sein. Wichtig ist, dass die (Gedanken-)Urne so mit Kugeln befüllt wird, dass sie die Aufgabenstellung korrekt widerspiegelt.
Die Anzahl der Kugeln in dieser Urne wird mit $n$ bezeichnet, das ist die Grundgesamtheit der Stichprobe. Das Auswählen der Schüler, Läufer etc. wird nun dadurch dargestellt, dass wir Kugeln aus dieser Urne entnehmen. Wir entnehmen insgesamt k Kugeln, das ist der Stichprobenumfang.
Beispiel: Wir spielen Karten
Ein klassisches Uno-Spiel enthält 4 Farben mit je 19 Karten, dazu pro Farbe jeweils 2 Sonder-Farbkarten für die Aktionen „Aussetzen“, „Richtungswechsel“ und „Nimm 2“. Außerdem gibt es 8 schwarze Sonderkarten. Jeder Spieler erhält zu Beginn 7 Karten. Wie viele der möglichen Kartensätze enthalten genau eine „+2“-Karte?
Schritte zur Lösung: Das sind viele Zahlen, viele Farben, viele Informationen – insgesamt eine unübersichtliche Situation. Deshalb nehmen wir gedanklich jetzt eine Urne und befüllen sie mit Kugeln, die nur das unterscheiden, was uns wichtig ist. Wir interessieren uns für die „+2“-Karten, von denen es 8 gibt. Also befüllen wir die Urne mit 8 roten Kugeln. Die Farbe „rot“ ist willkürlich gewählt und dient nur der Unterscheidung der Kugeln. Außerdem gibt es 100 weitere Karten, deren Unterscheidung für unser Problem nicht relevant ist. Dafür tun wir 100 blaue Kugeln in die Urne.
Variationen und Kombinationen
Neben dem korrekten Befüllen der Urne müssen wir uns bei jeder Aufgabe zwei Fragen beantworten:
- Spielt die Reihenfolge der Ziehungen eine Rolle? Geordnete Stichproben heißen Variationen, und ungeordnete Stichproben heißen Kombinationen.
- Wird nach jedem Wurf die gezogene Kugel wieder zurückgelegt? Wenn ja, haben wir vor jedem Wurf die gleichen Ausgangsbedingungen. Wir sprechen von Ziehen mit Zurücklegen oder einer Stichprobe mit Wiederholung. Wenn die Kugel nicht wieder zurückgelegt wird, haben wir Ziehen ohne Zurücklegen oder eine Stichprobe ohne Wiederholung. In diesem Fall reduziert sich bei jedem Zug die Zahl der Kugeln einer Farbe und damit auch die Gesamtzahl der Kugeln im Topf.
Das „Uno“-Urnenmodell
Für das Beispiel „Uno“ entnehmen wir der Urne 7 Karten, weil ein Spieler 7 Handkarten erhält. Und wir ziehen ohne Zurücklegen, weil man dieselbe Karte nicht zweimal erhält. Unser Ziel ist: Von den 7 Kugeln sollen genau 2 Kugeln rot sein. Damit können wir nun die vollständige Urnen-Aufgabe formulieren:
In einer Urne befinden sich 8 rote und 100 blaue Kugeln. Wie viele Möglichkeiten gibt es, daraus 7 Kugeln ohne Zurücklegen zu ziehen, so dass in der Stichprobe genau 2 rote Kugeln enthalten sind?
Das Urnenmodell entfernt also alle überflüssigen Informationen aus dem Problem und reduziert es auf eine Standard-Aufgabe, die wir mit Standardmethoden lösen können. Diese Standardmethoden sind vier verschiedene Formeln, welche die Fälle geordnete/ungeordnete Stichprobe mit/ohne Wiederholung abdecken.
Wir bestimmen also die Parameter $n$ für die Gesamtzahl der Kugeln und $k$ für die Anzahl Kugeln mit dem gewünschten Merkmal. Dann wenden wir eine von vier Formeln an. Diese Formeln nehmen wir schon mal vorweg und werden sie auf den nächsten Seiten ausführlich erarbeiten. Wenn du wissen willst, wie die Formeln zustande kommen, oder Anwendungsbeispiele sehen willst, klick einfach auf die jeweilige Formel!
| mit Wiederholung | ohne Wiederholung | |
| geordnete Stichprobe (Variation) | $\displaystyle n^k$ | $\displaystyle\frac{n!}{(n-k)!}$ |
| ungeordnete Stichprobe (Kombination) | $\displaystyle \binom{n+k-1}{k}$ | $\displaystyle \binom{n}{k}$ |
Die Lösung des Uno-Problems
In