Kombinatorische Abzählverfahren

Einen guten Überblick darüber, womit sich die Kombinatorik beschäftigt zeit Daniel Jung in folgendem Video.

Sehr häufig wird das Urnenmodell zurate gezogen, wenn kombinatorische Abzählverfahren verwendet werden.

In einer Urne befinden sich $n$ Kugeln. Per Zufall (also ohne dabei zu sehen oder aussuchen) werden k davon herausgezogen.

Bemerkung: Bei manchen Experimenten macht es Sinn alle Kugeln voneinander unterscheiden zu können. Bei anderen Experimenten ist es nicht so wichtig. Dafür stellt man sich entweder vor,

• dass jede Kugel eine eindeutige Nummer bekommt oder,
• dass jede Kugel eine Farbe hat (die sich aber wiederholen kann).¹⁾

Ziehen mit Zurücklegen

Beim Ziehen mit Zurücklegen wird die Kugel nach jedem Ziehen zurückgelegt. Beispiele sind hier:

• Kombinationen bei einem Zahlenschloss
• Würfeln mit einem Würfel
• Wurf einer Münze
• …

Ziehen ohne Zurücklegen

Beim Ziehen ohne Zurücklegen wird die Kugel nach einem Versuch nicht wieder zurückgelegt. Beispiele sind hier:

• Positionierungen bei Wettrennen
• Ziehen von Lottokugeln
• …

Aus den Unterscheidungen von oben ergeben sich insgesamt vier verschiedene Fälle, die da wären:

1. Ziehen mit Zurücklegen mit Beachtung der Reihenfolge
2. Ziehen ohne Zurücklegen mit Beachtung der Reihenfolge
3. Ziehen ohne Zurücklegen ohne Beachtung der Reihenfolge
4. Ziehen mit Zurücklegen ohne Beachtung der Reihenfolge³⁾

Beim Ziehen ohne Zurücklegen werden die Kugeln nicht wieder in die Urne zurück gelegt. Somit ändert sich die Anzahl der Möglichkeiten nach dem Ziehen. Die Beachtung der Reihenfolge hat zur Folge, dass z.B. die Tupel $(1 ; 2; 3)$ und $(1; 3; 2)$ nicht gleich sind.

Sprinter

Ein Beispiel für diesen Fall ist die Anzahl möglicher Kombinationen der Platzierungen bei einem Sprintrennen. Angenommen es nehmen 8 Sprinter an dem Rennen teil, dann können alle 8 den ersten Platz belegen. Für den zweiten Platz bleiben dann noch 7 Möglichkeiten usw.

Es ergeben sich somit $8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 40320$ Kombinationsmöglichkeiten bzw. Permutationen. Die Kurzschreibeweise an dieser Stelle lautet $8! = 40320$ [gesprochen: 8 Fakultät…].

Zumeist interessieren bei einem Rennen nur die ersten drei Positionierungen. Es müssten also lediglich die ersten drei Positionen angeschaut werden also $8 \cdot 7 \cdot 6 = 336$.

Eine ebenfalls mögliche Rechnung ist folgende:

$N = \frac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 }{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 } = \frac{8 \cdot 7 \cdot 6 \cdot 5!}{(8 - 3)!} = \frac{8 \cdot 7 \cdot 6 \cdot 5!}{5!} = 8 \cdot 7 \cdot 6 = 336$

Boah, das ist doch jetzt echt nicht nötig das so kompliziert zu machen oder?

Doch, es wird sich gleich zeigen, warum das sinnvoll ist. In diesem Fall werden die "überschüssigen" $5!$ Möglichkeiten durch Kürzen weggenommen, da sie im Zähler und im Nenner stehen. Dies ist insofern spannend, als dass es eine allgemeine Formel für Aufgaben dieser Art eröffnet.

Video zum Beispiel

Das Ziehen ohne Zurücklegen ohne Beachtung der Reihenfolge verhält sich zunächst ähnlich dem Ziehen ohne zurücklegen mit Beachtung der Reihenfolge. Es müssen hier jedoch die verschiedenen Permutationen beachtet werden. Was heißt das konkret?

Verschiedene Reihenfolgen mit den gleichen Elementen zählen hier nun nicht mehr als eigene Ereignisse. Betrachten wir hier ein Beispiel:

Ob ich beim Lotto die Zahlen $(1; 3; 37; 42; 47; 11)$ oder die Zahlen $(1; 3; 11; 37; 42; 47)$ tippe macht keinen Unterschied. Somit zählen alle Möglichkeiten, die aus den oben genannten Zahlen zusammengesetzt sind als eine Möglichkeit.

Wieviele solcher Kombinationen gibt es? Hier hilft die Überlegung von weiter oben zum Ziehen ohne Zurücklegen ohne Beachtung der Reihenfolge. Genau so eine Rechnung haben wir hier. Alle möglicheen Permutationen der Elemente findet man über folgende Betrachtung:

Lotto

Wie bereits erwähnt, ist das Lotto-Spiel "6 aus 49" ein gutes Beispiel für das Ziehen ohne Zurücklegen ohne Berücksichtigung der Reihenfolge. Die Frage ist hier: Wie viele Möglichkeiten gibt es bei "6 aus 49" zu tippen?

Zunächst rechnen wir hier:

$N = 49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 = 10068347520$

Moment mal, dass sieht doch aus wie beim Ziehen ohne Zurücklegen mit Beachtung der Reihenfolge oder?

Korrekt, auch hier ließe sich die Formel von oben anwenden wenn wir $n=49$ und $k=6$ wählen:

$\begin{align} N &= \frac{n!}{(n-k)!}\\ &= \frac{49!}{(49 - 6)!}\\ &= \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \cdot 43!}{43!} \\ &= 49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \\ \\ &= 10068347520 \end{align}$

Bisher ist jedoch die Reihenfolge der Elemente noch berücksichtigt. Die Anzahl der Möglichkeiten ist also noch etwas geringer. Wir habean uns bereits Gedanken dazu gemacht, wie viele Möglichkeiten es gibt eine Menge aus 6 Elementen anzuordnen nämlich $6!$. Durch $6!$ müssen wir nun noch dividieren, da wir alle Permutationen der 6-elementigen Teilmengen nun als eine werten müssen. Insgesamt ergibt sich daraus folgende Rechnung:

$\begin{align} N &= \frac{49!}{6! \cdot (49 - 6)!}\\ &= \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \cdot 43!}{6! \cdot 43!} \\ &= \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6!} \\ &= 13983816 \\ \end{align}$

Das klingt nicht nach der Zahl, die ich aus dem Radio kenne?
Richtig, bei unserer Rechnung fehlt die Superzahl.

Insgesamt gibt es also beim Spiel "6 aus 49" $13983816$ Möglichkeiten zu tippen. Eine allgemeine Form für Fragen dieser Art ergibt folgt im nächsten Abschnitt.

Video zum Beispiel

Der Fall ohne Zurücklegen und ohne Berücksichtigung der Reihenfolge kommt häufig vor. Da die Berechnung dieses Falls des Urnenmodells im Vergleich zu den anderen aufwändiger ist, gibt es für diesen Fall eine eigene Form der Darstellung, den sogenannten Binomialkoeffizienten. Die Formel hier lautet wie folgt: