Was ist Kombinatorik?

Für viele Wahrscheinlichkeiten muss man zählen: Wie viele Ergebnisse hat ein Zufallsexperiment, und wie viele davon gehören zu einem Ereignis {A}? Beim Laplace-Experiment ist die Wahrscheinlichkeit genau der Quotient aus diesen beiden Anzahlen. Die Kombinatorik ist die Kunst des geschickten Zählens: Sie liefert Formeln, mit denen man solche Anzahlen berechnet, ohne alle Möglichkeiten aufzuschreiben.

Vier typische Zählfragen

Die Zählaufgaben kommen aus ganz verschiedenen Gebieten:

  • Wie viele Ergebnisse gibt es, wenn man dreimal würfelt und die Reihenfolge der Würfe beachtet?
  • Wie viele Möglichkeiten gibt es, bei einem Lauf mit 8 Läufern Gold, Silber und Bronze zu vergeben?
  • Wie viele Möglichkeiten gibt es, aus den 24 Schülern einer Klasse einen dreiköpfigen Ausschuss für die Klassenfahrt zu wählen?
  • Auf wie viele Arten kann man aus drei Getränkesorten eine Kiste mit 12 Flaschen zusammenstellen?

Auf den ersten Blick haben diese Fragen wenig gemeinsam. Mit dem Urnenmodell lassen sie sich aber alle auf dieselbe Situation zurückführen.

Das Urnenmodell

Statt mit Würfeln, Läufern oder Getränken rechnen wir mit einer Urne, einem Topf voller Kugeln. Für jede Möglichkeit, also jede Augenzahl, jeden Läufer oder jede Sorte, liegt eine Kugel in der Urne. Unterscheidbare Dinge bekommen unterscheidbare Kugeln, zum Beispiel mit Nummern. Jede Auswahl entspricht dem Ziehen einer Kugel.

124563gezogen

Die Anzahl der Kugeln in der Urne heißt Grundgesamtheit {n}, die Anzahl der Ziehungen Stichprobenumfang {k}. Um die passende Formel zu finden, stellt man zwei Fragen:

Die zwei Fragen der Kombinatorik:

  • Spielt die Reihenfolge eine Rolle? Dann ist es eine geordnete Stichprobe, sonst eine ungeordnete.
  • Darf dasselbe mehrfach vorkommen? Dann ziehen wir mit Zurücklegen (mit Wiederholung), sonst ohne Zurücklegen (ohne Wiederholung).

Aus den beiden Antworten ergeben sich vier Fälle mit je einer Formel.

Die vier Formeln im Überblick

Für jeden der vier Fälle gibt es eine Formel für die Anzahl der Möglichkeiten:

mit Zurücklegenohne Zurücklegen
geordnet{n^k}{\dfrac{n!}{(n-k)!}}
ungeordnet{\dbinom{n+k-1}{k}}{\dbinom{n}{k}}

Darin stecken die Fakultät {n!} und der Binomialkoeffizient {\binom nk}. Jede Formel wird in einem eigenen Artikel hergeleitet. Alle beruhen auf der Produktregel der Kombinatorik. Mit ihr kommst du auch dann weiter, wenn du eine Formel einmal vergessen hast. Deshalb ist sie der beste nächste Schritt.

Übersetze die vier Zählfragen vom Anfang in ein Urnenmodell: Wie groß sind {n} und {k}, ist die Stichprobe geordnet oder ungeordnet, mit oder ohne Zurücklegen? Berechne dann die Anzahl mit der Tabelle.

Hinweis

Beim Ausschuss sind alle drei Mitglieder gleichberechtigt. Bei der Getränkekiste ist eine Kugel eine Sorte, und dieselbe Sorte darf mehrfach vorkommen.

Lösung
  • Dreimal würfeln: {n=6}, {k=3}, geordnet, mit Zurücklegen: {6^3=216} Ergebnisse.
  • Medaillen: {n=8}, {k=3}, geordnet, ohne Zurücklegen: \frac{8!}{5!}=8\cdot 7\cdot 6=336 Möglichkeiten.
  • Ausschuss: {n=24}, {k=3}, ungeordnet, ohne Zurücklegen: {\binom{24}{3}=2024} Möglichkeiten.
  • Getränkekiste: {n=3}, {k=12}, ungeordnet, mit Zurücklegen: {\binom{14}{12}=91} Möglichkeiten.