11. Kombinatorik

Einführung und Motivation

Wir stellen uns dazu $n$ unterscheidbare Kugeln (nummerierte Lottokugeln) in einer Urne vor, aus denen nun nacheinander $k$ Kugeln gezogen werden. Wenn Wahrscheinlichkeiten interessieren, soll bei jedem Zug die Wahrscheinlichkeit für jede Kugel gleich sein ("blind ziehen"), zum Anzählen der Möglichkeiten reicht es, wenn in jedem Zug jede Kugel drankommen kann. Im Folgenden seien $n, k\in\mathbb{N}_0$, wobei wir $0^0 = 0! = 1$ setzen.

Für den Versuchsaufbau sind zwei Entscheidungen zu treffen:

• man kann die gezogene Kugel wieder in die Urne zurücklegen (nachdem man sich die Nummer notiert hat…) oder nicht und

• man kann sich beim Ergebnis dafür interessieren, in welcher Reihenfolge die Kugeln gezogen wurden oder nicht (letztes trifft z.B. beim Lotto zu, wo die Lottogesellschaft uns die Zahlen sortiert).

Somit sind vier verschiedene Fälle zu betrachten.

Ziehen mit Zurücklegen, mit Berücksichtigung der Reihenfolge

Wenn wir die Kugeln wieder zurückwerfen, haben wir in jedem der $k$ Züge $n$ Möglichkeiten.

Das ist also wie in der Aufgabe mit den $2^k$ möglichen Zuständen von $k$ Bit, nur dass dort der Spezialfall $n=2$ untersucht wurde.

Ziehen ohne Zurücklegen, mit Berücksichtigung der Reihenfolge

Jetzt werfen wir gezogene Kugeln nicht wieder zurück.

Dann haben wir im ersten Zug nach wie vor $n$ Kugeln, im zweiten Zug aber nur noch $n-1$, im dritten $n-2$, $\ldots$, im letzten ($k$-ten) Zug noch $n-k+1$ Kugeln zur Auswahl.

Beim $j$-ten der $k$ Züge also $n-j+1$ Möglichkeiten, also insgesamt

mögliche Ergebnisse.

Ziehen ohne Zurücklegen, ohne Berücksichtigung der Reihenfolge

Jetzt sortieren wir die Kugeln nach ihrer Nummerierung, bevor wir das Ergebnis verkünden - die Zugfolgen $(15, 4, 8)$ und $(4, 8, 15)$ zählen nun als gleich, wir sind also beim klassischen Lotto. Wie viele Möglichkeiten gibt es nun noch?

Ziehen mit Zurücklegen, ohne Berücksichtigung der Reihenfolge

Der schwierigste Fall zuletzt: wir werfen die Kugeln in die Urne zurück und identifizieren Zugfolgen, die sich nur in der Reihenfolge unterscheiden, d.h., wir interessieren uns nur dafür, wie oft welche Kugel gezogen wird.

Zum Beweis ersetzen wir das ursprüngliche Modell mit Kugeln und Zellen durch ein anderes Modell:

$n+k-1$ Positionen. Verteile $n-1$ Striche auf diese Positionen. Alle Positionen ohne Strich erhalten $\ast$ (einen Stern).

Auf diese Art und Weise kann jedes mögliche Ereignis des ursprünglichen Urnenmodells eindeutig codiert werden.

Nun interpretieren wir dieses Strich-Modell wieder als ein Urnenmodell: Kugeln $=$ mögliche Positionen von $1{,}2,\ldots,n+k-1$. Gezogen werden $n-1$ Kugeln ohne Zurücklegen und ohne Berücksichtigung der Reihenfolge. Jede gezogene Kugel ist eine Position der $n-1$ Striche.