Grundbegriffe der Kombinatorik

Was ist Kombinatorik?

Wer Wahrscheinlichkeiten berechnen will, muss zählen können: Wie viele Dinge einer bestimmten Art gibt es? Wie viele davon haben eine geforderte Eigenschaft? Dazu ein kleines Beispiel:

Wie groß ist die Wahrscheinlichkeit, dass beim Wurf mit einem Würfel eine 4 fällt?

Um diese Frage zu beantworten, müssen wir zwei Dinge wissen: Wie viele Seiten hat der Würfel? Es sind 6. Und wie viele davon zeigen eine 4? Eine! Damit beträgt die gesuchte Wahrscheinlichkeit 1/6. Solch ein Experiment, bei dem alle Ergebnisse die gleiche Chance haben, dranzukommen, heißt Laplace-Experiment. Aber dazu später mehr.

Bei der Würfelaufgabe konnten wir die Zahl der Möglichkeiten einfach durchzählen. Meistens ist das nicht so einfach. Deshalb gibt es ein paar Formeln, die uns dabei helfen. Das Themengebiet, das diese Formeln bereitstellt, heißt Kombinatorik.

Zwei mathematische Objekte helfen uns dabei: die Fakultät und der Binomialkoeffizient. Beide werden wir im folgenden ausführlich erklären. Außerdem entwickeln wir vier Formeln, mit denen wir die Anzahl Elemente (die "Mächtigkeit") einer Menge berechnen können. Und natürlich besprechen wir, wie man denn erkennt, wann welche Formel angewendet wird.

Geordnete Stichprobe mit Wiederholung

Nun aber gleich ans Eingemachte. Wir ignorieren zunächst die Überschrift und schauen uns folgende Aufgabe an:

Ein Würfel wird dreimal geworfen und jeweils die Augenzahl notiert. Wie viele Zahlenfolgen können dabei entstehen?

Ein Versuch, bei dem etwas mehrfach durchgeführt wird, heißt mehrstufiges Experiment. Wir schauen uns die Durchführungen einzeln an:

  • Im ersten Versuch gibt es 6 Möglichkeiten - die 6 Augenzahlen.
  • Im zweiten Versuch gibt es auch 6 Möglichkeiten, denn auch die bereits gewürfelte Zahl kann wieder drankommen.
  • Auch im dritten Versuch gibt es 6 Möglichkeiten.

Die Ergebnisse aller drei Versuche können beliebig miteinander kombiniert werden, daher gibt es insgesamt

$$6\cdot 6\cdot 6=6^3$$

mögliche Zahlenfolgen. Allgemein können wir für diesen Fall formulieren:

Aus einer Menge mit n Elementen werden k ausgewählt, und zwar mit Berücksichtigung der Reihenfolge und mit Wiederholung. Dann gibt es nk Auswahlmöglichkeiten.

Mit dieser Formel können wir diese und weitere Aufgaben nun schneller lösen:

Ein Glücksrad mit 6 gleich großen und verschieden farbigen Sektoren wird dreimal gedreht und jeweils die erdrehte Farbe notiert. Wie viele Kombinationen sind möglich? Bei wie vielen davon ist die erste Farbe rot? Dabei gehen wir natürlich davon aus, dass es auch einen roten Sektor gibt.

Zur ersten Frage: Wir erkennen, dass es eine geordnete Stichprobe ist, da die Ergebnisse in der Reihenfolge des Auftretens notiert werden. Und es ist mit Wiederholung, denn alle Farben können bei den weiteren Drehs wieder auftauchen. Es ist n = 6, denn es gibt in jeder Stufe 6 Auswahlmöglichkeiten. Und es ist k = 3, denn es wird dreimal gedreht. Damit gibt es insgesamt 63 mögliche Ergebnisse.

Auch wenn wir die Formel so klar anwenden können wie in diesem Beispiel, sollten wir uns immer daran erinnern, wie sie entstanden ist: nämlich durch Multiplikation der Möglichkeiten in jeder Stufe. Dann können wir die Rechnung an veränderte Aufgabenstellungen anpassen, wie die zweite Frage zeigt:

Wenn die erste Farbe "rot" sein soll, gibt es in dieser Runde nur eine Möglichkeit. Die weiteren Runden haben dann wieder 6 Ergebnisse, und die Gesamtzahl der Möglichkeiten mit "Erster Dreh rot" ist:

1 x 6 x 6 = 36

Fakultät

An einem 100m-Lauf nehmen 5 Schüler teil. Wie viele Möglichkeiten des Zieleinlaufs gibt es?

Lösung: Für den ersten Platz gibt es 5 Möglichkeiten, für den zweiten noch 4, dann 3, 2, 1, also gibt es insgesamt 5 x 4 x 3 x 2 x 1 Möglichkeiten des Zieleinlaufs. Diese Rechnung, bei der die Zahlen von 1 bis zu einer Zahl n multipliziert werden, kommt sehr oft vor, daher bekommt sie ein eigenes Rechenzeichen. Wir definieren für alle natürlichen Zahlen n:

n! = 1 x 2 x 3 x ... x n

und nennen den Term "n Fakultät". Die Anzahl der möglichen Zieleinläufe mit 5 Teilnehmern ist also kurz 5!.

Geordnete Stichprobe ohne Wiederholung

Am olympischen 100m-Finale nehmen 8 Läufer teil. Wie viele Möglichkeiten der Medaillenvergabe für Gold, Silber und Bronze gibt es?

Wir schauen die Medaillenplätze wieder einzeln an: Für den ersten Platz gibt es 8 Möglichkeiten, für den zweiten noch 7 und für den dritten 6. Also gibt es 8 x 7 x 6 Möglichkeiten der Medaillenvergabe.

Diese Lösungsformel können wir mit Fakultäten schreiben, obwohl die Zahlenfolge nicht bei 1 beginnt:

$$8\cdot 7\cdot 6=\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!}{5!}$$

Anhand dieser Aufgabe wollen wir eine Formel entwickeln, wie wir solche Aufgaben allgemein lösen können. Es handelt sich um eine geordnete Stichprobe, da die Reihenfolge des Zieleinlaufs entscheidend ist. Es gibt aber keine Wiederholung, denn jeder Läufer kommt nur einmal ins Ziel.

Wenn der Zieleinlauf aller Läufer betrachtet wird, gibt es 8! Möglichkeiten, das haben wir im vorigen Beispiel schon gesehen. Wenn aber nur die ersten drei Plätze entscheidend sind, dann führen die folgenden Zieleinläufe alle zu dem gleichen Ergebnis:

ABC DEFGH
ABC FHDGE
ABC EHGFD
...

Diese Fälle führen alle zur gleichen Medailllenvergabe und wurden bei den 8! Ergebnissen zu oft aufgeführt. Es gibt 5! Möglichkeiten, die weiteren Plätze mit den Läufern D,E,F,G,H zu besetzen. Also hat die obige Liste mit den Medaillen für A,B,C insgesamt 5! Einträge. Deshalb müssen wir die Gesamtliste mit 8! Einträgen durch 5! teilen und bekommen die Anzahl Möglichkeiten der Medaillenvergabe:

$$\frac{8!}{5!}=\frac{8\cdot 7\cdot 6\cdot\ldots\cdot 1}{5\cdot 4\cdot\ldots\cdot 1}=8\cdot 7\cdot 6$$

Allgemein werden aus n Elementen k ausgewählt und zwar mit Berücksichtigung der Reihenfolge und ohne Wiederholung. Wenn man alle auswählt, gibt es n! Möglichkeiten, dabei ist aber jede Anordnung der k Elemente nicht nur einmal berücksichtigt, sondern so oft, wie man die übrigen n-k Elemente anordnen kann., also (n-k)! Mal. Deshalb lauter die Formel für eine geordnete Stichprobe ohne Wiederholung:

$$\frac{n!}{(n-k)!}$$

About the author

Pretium lorem primis senectus habitasse lectus donec ultricies tortor adipiscing fusce morbi volutpat pellentesque consectetur risus molestie curae malesuada. Dignissim lacus convallis massa mauris enim mattis magnis senectus montes mollis phasellus.

Schreibe einen Kommentar