3.2.1 Grundformeln der Kombinatorik

Anzahl der Möglichkeiten

Will man die Wahrscheinlichkeit eines Ereignisses \(A\) eines Laplace-Experiments bestimmen, interessiert man sich für die Anzahl der Elemente des Ergebnisraums \(\Omega\) und die Anzahl der Elemente des Ereignisses \(A\) (vgl. 3.1.3 Laplace-Experiment, Laplace-Wahrscheinlichkeit). Hierfür liefert die Kombinatorik wichtige Abzählmethoden (vgl. Grundformeln der Kombinatorik), die auf dem allgemeinen Zählprinzip beruhen.

 

Allgemeines Zählprinzip

Wird ein Zufallsexperiment in \(k\) Stufen durchgeführt und gibt es in der ersten Stufe \(n_{1}\), in der zweiten Stufe \(n_{2}\) und in der \(k\)-ten Stufe \(n_{k}\) mögliche Ergebnisse, so gilt für die Anzahl \(N\) der insgesamt möglichen Ergebnisse:

\[N = n_{1} \cdot n_{2}\, \cdot \, ... \, \cdot \, n_{k}\]

 

 

Grundformeln der Kombinatorik

Viele mehrstufige Zufallsexperimente lassen sich mithilfe sogenannter Urnenmodelle veranschaulichen und simulieren. Aus einer Urne mit \(\boldsymbol{n}\) unterscheidbaren Kugeln wird \(\boldsymbol{k}\)-mal eine Kugel gezogen.

Je nach Modell werden die Kugeln mit oder ohne Zurücklegen gezogen und es wird außerdem darauf geachtet, ob die Reihenfolge der gezogenen Kugeln einen Rolle spielt.

Die nachfolgende Tabelle gibt für das jeweilige Urnenmodell den Term an, mit dem sich die Anzahl der möglichen Ergebnisse berechnen lässt.

  Mit Beachtung der Reihenfolge Ohne Beachtung der Reihenfolge
Mit Zurücklegen \(n^{k}\) - nicht abiturrelevant -
Ohne Zurücklegen

\(n \cdot (n - 1) \cdot ... \cdot (n - k + 1)\)

Spezialfall: \(n!\) für \(k = n\) (Permutationen)

\(\displaystyle \binom{n}{k} = \frac{n!}{k! \cdot (n - k)!}\)

(entspricht „Ziehen mit einem Griff", vgl. Binomialkoeffizient)

 

Binomialkoeffizient

Der Binomialkoeffizient gibt an, wie viele Möglichkeiten es gibt, aus einer Menge mit \(n\) Elementen eine Teilmenge mit \(k\) Elementen zu bilden.

\[\binom{n}{k} = \frac{n!}{k! \cdot (n - k)!} = \frac{n \cdot (n - 1) \cdot ... \cdot (n - k + 1)}{k!}\]

(vgl. Merkhilfe)

 

 

Beispielaufgaben

1. Beispielaufgabe

Wie viele Möglichkeiten gibt es, aus den Ziffern 0 bis 9 eine vierstellige Geheim-PIN zu bilden?

 

Für jede der vier Stellen der PIN stehen die Ziffern 0 bis 9 zur Verfügung, wobei die möglichen Zahlenkombinationen unterschieden werden. 

Urnenmodell mit Zurücklegen und mit Beachtung der Reihenfolge:

Aus einer Urne mit 10 unterscheidbaren Kugeln wird 4-mal mit Zurücklegen eine Kugel gezogen und in der Reihenfolge des Ziehens notiert.

 

\(n = 10\), \(k = 4\)

 

\[n^{k} = 10^{4} = 10000\]

 

2. Beispielaufgabe

Acht Läufer starten zu einem 400-Meter-Lauf. Wie viele Möglichkeiten gibt es für die Belegung der ersten drei Plätze, wenn die Läufer nacheinander durchs Ziel laufen?

 

Jeder Läufer kann nur einmal durchs Ziel laufen, wobei darauf geachtet wird, welcher Läufer als Erster, als Zweiter und als Dritter das Ziel erreicht. 

Urnenmodell ohne Zurücklegen und mit Beachtung der Reihenfolge:

Aus einer Urne mit 8 unterscheidbaren Kugeln wird 3-mal ohne Zurücklegen eine Kugel gezogen und in der Reihenfolge des Ziehens notiert.

 

\(n = 8\), \(k = 3\)

 

\[n \cdot (n -1) \cdot ... \cdot (n - k + 1) = 8 \cdot 7 \cdot (8 - 3 + 1) = 8 \cdot 7 \cdot 6 = 336\]

 

3. Beispielaufgabe

In einer Schulklasse sind 25 Schülerinnen und Schüler. Insgesamt 6 Schülerinnen und Schüler können an einer Studienfahrt teilnehmen. Wie viele Möglichkeiten gibt es, wenn die Teilnahme an der Studienfahrt verlost wird.

 

Eine Teilnahme an der Studienfahrt (ein Los) wird einmalig vergeben. Das Losverfahren unterscheidet nicht unter den Schülerinnen und Schülern.

Urnenmodell ohne Zurücklegen und ohne Beachtung der Reihenfolge:

Aus einer Urne mit 25 unterscheidbaren Kugeln werden 6 Kugel mit einem Griff gezogen (wird 6-mal eine Kugel ohne Zurücklegen und ohne Beachtung der Reihenfolge gezogen).

 

\(n = 25\), \(k = 6\)

 

\[\binom{n}{k} = \binom{25}{6} = \frac{25!}{6! \cdot (25 - 6)!} = 177100\]

 

4. Beispielaufgabe

Eine Prüfung besteht aus 12 Aufgaben. Sie gilt als bestanden, wenn mindestens 9 Aufgaben richtig gelöst wurden, wobei die ersten 4 Aufgabe darunter sein müssen. Auf wie viele verschieden Arten kann die Prüfung bestanden werden?

 

Die richtige Lösung der ersten 4 Aufgaben ist Pflicht für das Bestehen der Prüfung. Damit verbleiben noch 8 Aufgaben, von denen mindestens 5 Aufgaben richtig gelöst werden müssen. Mindesten 5 Aufgaben bedeutet 5, 6, 7 oder alle 8 Aufgaben. Jede Aufgabe wird einmalig bearbeitet. Welche der mindestens 5 Aufgaben gelöst werden spielt keine Rolle.

Urnenmodell ohne Zurücklegen und Ohne Beachtung der Reihenfolge:

Aus einer Urne mit 8 unterscheidbaren Kugeln werden 5 Kugeln (6, 7, 8 Kugeln) mit einem Griff gezogen.

 

\[\begin{align*}&\binom{8}{5} + \binom{8}{6} + \binom{8}{7} + \binom{8}{8} \\[0.8em] = \enspace &56 + 28 + 8 + 1 \\[0.8em] = \enspace &93\end{align*}\]

 

5. Beispielaufgabe

Ein Kennzeichen für eine Produktlinie beginnt mit drei Buchstaben worauf drei Ziffern folgen. Die erste Ziffer darf keine 0 sein. Wie viele verschiedene Kennzeichen sind möglich, wenn die Buchstaben wie auch die Ziffern mehrfach vorkommen dürfen.

 

Das Entstehen eines Kennzeichens kann als 3-stufiges Zufallsexperiment aufgefasst werden, wobei beispielsweise die drei Buchstaben die erste Stufe, die nachfolgende erste Ziffer die zweite Stufe und die verbleibenden zwei Ziffern die dritte Stufe bilden.

 

Mögliche Buchstabenkombinationen (1. Stufe)

Für die ersten drei Kennziffern des Kennzeichens stehen jeweils 26 Buchstaben zur Verfügung, wobei die möglichen Buchstabenkombinationen unterschieden werden.

Urnenmodell mit Zurücklegen und mit Beachtung der Reihenfolge:

Aus einer Urne mit 26 unterscheidbaren Kugel wird 3-mal mit Zurücklegen eine Kugel gezogen und in der Reihenfolge des Ziehens notiert.

 

\(n = 26\), \(k = 3\)

 

\[n^{k} = 26^{3} = 17576\]

 

Mögliche erste Ziffer (2. Stufe)

Für die erste Ziffer gibt es 9 Möglichkeiten.

 

Mögliche Zahlenkombinationen der verbleibenden drei Ziffern (3. Stufe)

Für jede der verbleibenden zwei Ziffern gibt es jeweils 10 Möglcihkeiten. Die möglichen Ziffernkombinationen werden unterschieden.

Urnenmodell mit Zurücklegen und mit Beachtung der Reihenfolge:

Aus einer Urne mit 10 unterscheidbaren Kugel wird 2-mal mit Zurücklegen eine Kugel gezogen und in der Reihenfolge des Ziehens notiert.

 

\(n = 10\), \(k = 2\)

 

\[n^{k} = 10^{2} = 100\]

 

Mögliche verschiedene Kennzeichen

Nach dem allgemeinen Zählprinzip werden die Möglichkeiten der einzelnen Stufen des Zufallsexperiments multipliziert.

 

\[17576 \cdot 9 \cdot 100 = 15818400\]

 

6. Beispielaufgabe

Ein Kind bildet mit 3 roten, 4 gelben und 5 blauen Bauklötzen eine Reihe. Alle Bauklötze tragen verschiedene Symbole. Wie viele mögliche Anordnungen gibt es, wenn

a) nur nach den Symbolen unterschieden wird.

b) nur nach der Farbe unterschieden wird.

 

a) Möglichkeiten, wenn nur nach den Symbolen unterschieden wird

Es gibt insgesamt 12 Bausteine, von denen jeder einmal abgelegt wird. Die möglichen Anordnungen der Symbole werden unterschieden.

Urnenmodell ohne Zurücklegen und mit Berücksichtigung der Reihenfolge:

Aus einer Urne mit 12 unterscheidbaren Kugeln wird 12-mal eine Kugel ohne Zurücklegen gezogen und in der Reihenfolge des Ziehens notiert.

 

\(n = 12\), \(k = 12\)

 

\(n \cdot (n - 1) \cdot ... \cdot (n - k +1) = n! = 12! = 479001600\)

 

b) Möglichkeiten, wenn nur nach den Farben unterschieden wird

Das Anordnen der Bauklötze in einer Reihe kann als 3-stufiges Zufallsexperiment aufgefasst werden, wobei beispielsweise das Ablegen der 3 roten Bauklötze die erste Stufe, das Ablegen der 4 gelben Bauklötze die zweite Stufe und das Ablegen der 5 grünen Bauklötze die dritte Stufe bildet.

 

Möglichkeiten, die 3 roten Bauklötze anzuordnen (1. Stufe)

Jeder der 3 roten Bauklötze wird einmalig abgelegt, ohne dass diese untereinander nach den Symbolen unterschieden werden. Dafür stehen zu Beginn 12 „Plätze" in der Reihe zur Verfügung.

Urnenmodell ohne Zurücklegen und Ohne Beachtung der Reihenfolge:

Aus einer Urne mit 12 unterscheidbaren Kugeln werden 3 Kugeln mit einem Griff gezogen (wird 3-mal eine Kugel ohne Zurücklegen und ohne Beachtung der Reihenfolge gezogen).

 

\(n = 12\), \(k = 3\)

 

\[\binom{n}{k} = \binom{12}{3} = \frac{12!}{3! \cdot (12 - 3)!} = 220\]

 

Möglichkeiten, die 4 gelben Bauklötze anzuordnen (2. Stufe)

Jeder der 4 gelben Bauklötze wird einmalig abgelegt, ohne dass diese untereinander nach den Symbolen unterschieden werden. Dafür verbleiben noch 9 „Plätze" in der Reihe.

Urnenmodell ohne Zurücklegen und Ohne Beachtung der Reihenfolge:

Aus einer Urne mit 9 unterscheidbaren Kugeln werden 4 Kugeln mit einem Griff gezogen (wird 4-mal eine Kugel ohne Zurücklegen und ohne Beachtung der Reihenfolge gezogen).

 

\(n = 9\), \(k = 4\)

 

\[\binom{n}{k} = \binom{9}{4} = \frac{9!}{4! \cdot (9 - 4)!} = 126\]

 

Möglichkeiten, die 5 grünen Bauklötze anzuordnen (3. Stufe)

Jeder der 5 grünen Bauklötze wird einmalig abgelegt, ohne dass diese untereinander nach den Symbolen unterschieden werden. Dafür verbleiben noch 5 „Plätze" in der Reihe.

Urnenmodell ohne Zurücklegen und Ohne Beachtung der Reihenfolge:

Aus einer Urne mit 5 unterscheidbaren Kugeln werden 5 Kugeln mit einem Griff gezogen (wird 5-mal eine Kugel ohne Zurücklegen und ohne Beachtung der Reihenfolge gezogen).

 

\(n = 5\), \(k = 5\)

 

\[\binom{n}{k} = \binom{5}{5} = \frac{5!}{5! \cdot (5 - 5)!} = 1\]

 

Möglichkeiten, die Bauklötze nach unterschiedlichen Farben anzuordnen

Nach dem allgemeinen Zählprinzip werden die Möglichkeiten der einzelnen Stufen des Zufallsexperiments multipliziert.

 

\[220 \cdot 126 \cdot 1 = 27720\]

 

Alternative Vorgehensweise

Die unter a) aufgeführten Möglichkeiten, die Bauklötze nach verschiedenen Symbolen anzuordnen, berücksichtigen auch die verschiedenen Anordnungen nach Symbolen der Bauklötze einer Farbe untereinander. Teilt man nun die Möglichkeiten, die Bauklötze nach Symbolen anzuordnen durch die Möglichkeiten, die Bauklötze einer Farbe untereinander nach Symbolen anzuordnen (Permutationen), so erhält man die Anzahl der möglichen Anordnungen, wenn nur nach der Farbe unterschieden wird.

 

Möglichkeiten, die Bauklötze einer Farbe untereinander nach Symbolen anzuordnen

Betrachtet man beispielsweise die 3 roten Bauklötze für sich, so werden diese einmalig abgelegt und auf die Anordnung deren Symbole geachtet. Diese Betrachtungsweise lässt sich auf die gelben und die grünen Bauklötze übertragen.

Urnenmodell ohne Zurücklegen und mit Beachtung der Reihenfolge:

Aus einer Urne mit 3 Kugeln (4 Kugeln, 5 Kugeln) wird 3-mal (4-mal, 5-mal) eine Kugel ohne Zurücklegen gezogen und diese in der Reihenfolge des Ziehens notiert.

 

Möglichkeiten, die 3 roten Bauklötze untereinander nach Symbolen anzuordnen

 

\(n = 3\), \(k = 3\)

 

\[n \cdot (n - 1) \cdot (n - k +1) = n! = 3! = 6\]

 

Möglichkeiten, die 4 gelben Bauklötze untereinander nach Symbolen anzuordnen

 

\(n = 4\), \(k = 4\)

 

\[n \cdot (n - 1) \cdot (n - k +1) = n! = 4! = 24\]

 

Möglichkeiten, die 5 grünen Bauklötze untereinander nach Symbolen anzuordnen

 

\(n = 5\), \(k = 5\)

 

\[n \cdot (n - 1) \cdot (n - k +1) = n! = 5! = 120\]

 

Möglichkeiten, die Bauklötze nach unterschiedlichen Farben anzuordnen

 

\[\begin{align*}&\frac{\text{Möglichkeiten (Symbole)}}{\text{Möglichkeiten (Symbole der Farben untereinander)}} \\[0.8em] = \enspace &\frac{479001600}{6 \cdot 24 \cdot 120} \\[0.8em] = \enspace &27720 \end{align*}\]