Wissen: Kombinatorik

Autor: Dr. Volkmar Naumburger ❤️ Bedanken

Leibnitz’ Irrtum – Über die Kunst, richtig zu zählen

Gottfried Wilhelm Leibnitz (1646-1716) wunderte sich über folgende Beobachtung erfahrener Würfelspieler:
Beim Würfeln mit zwei Würfeln tritt die Augensumme neun häufiger auf als die Augensumme zehn.

Leibniz überlegte sich:

Für die Augensumme neun gibt es zwei Möglichkeiten,
3 + 6 = 9 und 4 + 5 = 9 .

Für die Augensumme zehn gibt es ebenfalls zwei Möglichkeiten,

4 + 6 = 10 und 5 + 5 = 10 .

Also müssten eigentlich beide Augensummen gleich häufig auftreten!? Dennoch spricht die oben gemachte Erfahrung dafür, dass die Augensumme neun häufiger vorkommt als die Augensumme zehn.

Hätte Leibnitz „richtig“ gezählt, wäre ihm klar geworden, dass die einfache Logik versagt. Denn es gibt nur drei und nicht vier Möglichkeiten, mit zwei Würfeln eine 10 zu würfeln (siehe folgende Abbildung)!

Würfel Augensummen Kombinatorik Abbildung 19

Mit der Kunst des richtigen Zählens befasst sich das Teilgebiet der Kombinatorik. Diese wiederum spielt, wie es das Beispiel zeigt, eine wichtige Rolle in der Wahrscheinlichkeitsrechnung. Denn, um die Wahrscheinlichkeit für das Eintreffen eines bestimmten Ereignisses angeben zu können, wird die prinzipielle Häufigkeit, mit der das Ereignis eintreten kann, zur Gesamtzahl aller möglichen Ereignisse ins Verhältnis gesetzt. Wie groß nun die Häufigkeit der gewünschten Ereignisse ist hängt nun ganz stark von der Aufgabenstellung ab. Wichtig ist dabei auch, ob Elemente mehrfach verwendet auftreten können (mit Wiederholung) oder nicht (ohne Wiederholung). Im folgenden werden die drei wichtigsten Aufgabenstellungen betrachtet.

Permutation

Mit der Permutation (Vertauschung) wird die Anzahl aller möglichen Anordnungen der Elemente einer Grundmenge berechnet. Unterscheidungsmerkmal ist also die Reihenfolge der Elemente.

Aufgabe:

Alle N Elemente der Grundmenge werden in eine bestimmte Reihenfolge gebracht.

Fragestellung:

Wie viele Anordnungen (Permutationen) der Grundmenge gibt es?

Permutation ohne Wiederholung

Geltungsbereich:

1. Alle N Elemente der Ausgangsmenge sind unterscheidbar.

2. Es werden alle Elemente ausgewählt.

3. Die Reihenfolge ist wichtig.

4. Elemente können nicht mehrfach ausgewählt werden.

Fragestellung:

Wie viele unterschiedliche Permutationen gibt es?

Die Anzahl der Permutationen ohne Wiederholung errechnet sich nach

\( {P_N} = N! \quad \text{ mit } n! = 1 \cdot 2 \cdot 3 \cdot 4... \cdot n \) Gl. 73

Anhand der sog. Baumstruktur kann Gl. 73 für kleine Mengen (hier: 3 Elemente) überprüft werden:

Baumdiagramm - Baumstruktur Abbildung 20

Jedes Element der Grundmenge wird mit allen verbleibenden Elementen angeordnet. Jede Anordnung wird gezählt, d.h. die Reihenfolge ist wichtig.

Beispiel:

Bei einem Pferderennen wird auf den Einlauf in einer bestimmten Reihenfolge gewettet. 8 Pferde gehen an den Start. Wie groß ist die Wahrscheinlichkeit für die Platzierung 1-2-3-4-5-6-7-8?

Lösung:

\( \frac{1}{8!} ≈ 0,0025 \% \)

Permutation mit Wiederholung

Geltungsbereich:

1. Die N Elemente der Ausgangsmenge sind nicht alle unterscheidbar.

2. Es werden alle Elemente ausgewählt.

3. Die Reihenfolge ist wichtig.

4. Individuen können nicht mehrfach ausgewählt werden, Elemente schon.

Fragestellung:

Wie viele unterschiedliche Anordnungen (Permutationen) gibt es?

Die Anzahl der Permutationen mit Wiederholung errechnet sich nach

\( P_N^{ {k_1},{k_2},{k_3}...} = \frac{ {N!} }{ { {k_1}! · {k_2}! · {k_3}!...{k_n}!} } \) Gl. 74

Weil bestimmte Elemente mehrfach vorkommen, ist die Zahl der unterscheidbaren Anordnungen um die jeweiligen Permutationen der mehrfach vorkommenden Elemente geringer.

Zwischenbetrachtung – das Urnenmodell

Im Urnenmodell werden alle zu betrachtenden Elemente für den Ziehungsleiter unsichtbar in einer Urne untergebracht. Die Aufgabe besteht nun darin, stets alle Elemente aus der Urne zu entnehmen, deren Reihenfolge zu registrieren und

Permutationen bei Ziehung (Urnenmodell) Abbildung 21

anschließend wieder in die Urne zurück zu legen. Dies wird sooft wiederholt, bis alle möglichen unterscheidbaren Kombinationen gefunden worden sind.

Zwischenbetrachtung – das Baummodell

Die Baumstruktur für 3 Elemente, von denen zwei Elemente doppelt vorkommen:

Baumstruktur mit doppelten Elementen Abbildung 22

Beispiel 1:

Würde die ehemals sehr beliebte Pop-Gruppe ABBA ihren Namen als Grundlage für eine Komposition nehmen, wobei jedem Buchstaben der entsprechende Tonwert zuzuordnen ist, so ist die Frage wie viele unterschiedliche Klangfolgen sind aus den Buchstaben A (2x) und B (2x) ableitbar?

Lösung:

P=4!/(2!·2!) = 6 verschiedene Klangfolgen können aus A B B A erzeugt werden:

ABBA, BAAB, AABB, BBAA, ABAB, BABA

Aus diesem Beispiel wird klar, warum es sich hier um eine Permutation mit Wiederholung handelt: die Buchstaben A und B kommen wiederholt vor. Aber auch das folgende Beispiel fällt in diese Kategorie, auch wenn nicht auf den ersten Blick zu sehen ist, worin die Wiederholung besteht.

Beispiel 2:

Ein Skat-Spiel besteht aus 32 (unterscheidbaren) Karten. Nach dem Mischen erhalten die drei Spieler je 10 Karten und 2 Karten verbleiben im Skat. Wie viele unterschiedliche Kartenzusammensetzungen für ein Spiel gibt es?

Lösung:

P=32!/(10!·10!·10!·2!)= 2,75·1015 verschiedene Kartenkombinationen sind möglich, d.h. die Wahrscheinlichkeit für das Auftreten von zwei gleichen Spielen ist äußerst gering!

Die Anwendung der Permutation mit Wiederholung ist im Beispiel 2 darauf zurückzuführen, dass es für das Spiel unbedeutend ist, in welcher Reihenfolge die jeweils 10 Karten der Spieler oder der 2 Karten des Skats gegeben wurden. Die Anzahl dieser Permutationen vermindert die Anzahl der Gesamtpermutationen.

Beispiel 3:

Wie viele mögliche Kartenverteilungen im Skat gibt es?

Lösung:

P = 32!/(30!·2!) = 32·31/2 = 496

Kombination

Die Kombination (Zusammenstellung) zählt die möglichen Zusammenstellungen von Elementen ohne Ansehen der Reihenfolge. Zusammenstellungen mit gleichen Elementen werden nur einmal gezählt.

Aufgabe:

Aus N Elementen der Grundmenge werden k Elemente ausgewählt. Die Reihenfolge ist unwichtig.

Fragestellung:

Wie viele Zusammenstellungen (Kombinationen) von k Elementen aus der Grundmenge gibt es?

Kombination ohne Wiederholung

Geltungsbereich:

1. Alle N Elemente der Ausgangsmenge sind unterscheidbar.

2. Es werden k Elemente ausgewählt.

3. Die Reihenfolge ist unwichtig.

4. Elemente können nicht mehrfach ausgewählt werden.

Fragestellung:

Wie viele unterschiedliche Kombinationen von k aus N Elementen gibt es?

\( C_N^k = \frac{ {N!} }{ {(N - k)! \cdot k!} } \) Gl. 75

Gl. 75 berücksichtigt, dass die Anzahl aller möglichen Anordnungen (Permutation) um die Zahl der Anordnungen mit gleichen Elementen vermindert wird. Dies ist wieder anhand der Baumstruktur nachvollziehbar.

Anzahl möglicher Anordnungen (Permutation) um gleiche Elemente vermindert Abbildung 23

Erläuterung

Insgesamt sind von N Elementen N! prinzipiell verschiedene Anordnungen möglich. Nun werden aber nur k Elemente gezogen. Es gibt daher (N-k)! Permutationen der Restmenge und k! Permutationen der gezogenen Menge. Die Permutationen der Restmenge sind uninteressant und auch die Reihenfolge der Elemente der gezogenen Menge ist uninteressant. Daher reduziert sich die Gesamtzahl von Permutationen um die Anzahlen von Permutationen der Restmenge und der gezogenen Menge.

Permutationen und Ziehung Urne Abbildung 24

Beispiel:

Beim Gewinnspiel 6 aus 49 werden 6 Kugeln aus 49 durchnummerierten Kugeln gezogen. Keine der gezogenen Kugeln wird in das Spielgerät zurückgelegt. Wie groß ist die Wahrscheinlichkeit für einen Hauptgewinn?

Lösung:

C = 49!/(43!·6!) = 13.983.816. Die Wahrscheinlichkeit liegt also unter 10-5 %.

Kombination mit Wiederholung

Geltungsbereich:

1. Alle N Elemente der Ausgangsmenge sind unterscheidbar.

2. Es werden k Elemente ausgewählt.

3. Die Reihenfolge ist unwichtig.

4. Elemente können mehrfach ausgewählt werden.

Fragestellung:

Wie viele unterschiedliche Kombinationen gibt es?

\( C_N^k = \frac{ {(N + k - 1)!} }{ {(N - 1)! \cdot k!} } \) Gl. 76

Die Baumstruktur zeigt die Auswahl von k = 2 Elementen aus N = 3 Elementen:

Baumstruktur Möglichkeiten Auswahl Abbildung 25

Erläuterung

In einer Urne befinden sich N unterscheidbare Elemente. Es werden k Elemente eins nach dem anderen gezogen. Nach der Ziehung wird der Wert des Elementes notiert und in die Urne zurückgelegt, dann wird das nächste Element gezogen, dessen Wert notiert und wieder zurückgelegt. Dies wird für jedes der k Elemente getan. Indem nach jeder Ziehung das gezogene Element sofort zurückgelegt wird, können einzelne Elemente mehrfach gezogen werden.

Weil Elemente mehrfach gezogen werden können, erhöht sich die Anzahl der prinzipiell möglichen Permutationen auf (N+k-1). (k-1) weil es für k=1 keine Fallunterscheidung zwischen Kombination mit und ohne Wiederholung geben darf.

Die Anzahl der Permutationen der Restmenge beträgt (N-1)!, da stets nur ein Element aus der Urne entnommen wird. In der gezogenen Menge gibt es wieder k! Permutationen, da die Reihenfolge (auch wenn Elemente mehrfach vorkommen) unerheblich ist.

Anzahl der Permutationen der Restmenge (Reihenfolge unerheblich) Abbildung 26

Beispiel:

Ein Losverkäufer bietet rote, grüne, gelbe und blaue Lose zu je 1 € zum Verkauf an. Wie viele Loskombinationen können bei einem Budget von 3 € erworben werden?

Lösung:

C = (4+3-1)!/(4-1)!·3! = 6!/(3!·3!) = 20.

Variation

Die Variation (Abwandlung) greift Elemente aus einer Grundmenge heraus und ermittelt deren mögliche Kombinationen unter Beachtung der Reihenfolge.

Aufgabe:

Aus N Elementen der Grundmenge werden k Elemente ausgewählt. Die Reihenfolge ist dabei wichtig.

Fragestellung:

Wie viele Zusammenstellungen (Variationen) von k Elementen aus der Grundmenge unter Beachtung der Reihenfolge gibt es?

Variation ohne Wiederholung

Geltungsbereich:

1. Alle N Elemente der Ausgangsmenge sind unterscheidbar.

2. Es werden k Elemente ausgewählt.

3. Die Reihenfolge ist wichtig.

4. Elemente können nicht mehrfach ausgewählt werden.

Fragestellung:

Wie viele unterschiedliche Variationen von k aus N Elementen gibt es?

\( V_N^k = \frac{ {N!} }{ {(N - k)!} } \) Gl. 77

Die Baumstruktur mit den bekannten Ausgangsdaten N = 3 und k = 2 zeigt:

Baumstruktur mit Grundmenge N = 3 und k = 2 Abbildung 27

Beispiel:

Bei einem Pferderennen wird auf die Platzierung der ersten drei Pferde gewettet. 8 Pferde gehen an den Start. Wie groß ist die Wahrscheinlichkeit für die Platzierung 1. Platz - Nr. 1, 2. Platz - Nr. 2 und 3. Platz – Nr. 3?

Lösung:

V = 8!/(5!) = 336 Möglichkeiten gibt es für den Einlauf von 3 Pferden. D.h. die Wahrscheinlichkeit beträgt ca. 0,3 %.

Variation mit Wiederholung

Geltungsbereich:

1. Alle N Elemente der Ausgangsmenge sind unterscheidbar.

2. Es werden k Elemente ausgewählt.

3. Die Reihenfolge ist wichtig.

4. Elemente können mehrfach ausgewählt werden.

Fragestellung:

Wie viele unterschiedliche Variationen gibt es?

\( V_N^k = {N^k} \) Gl. 78

Die Baumstruktur zeigt die Auswahl von k = 2 Elementen aus N = 3 Elementen:

Baumstruktur mit Grundmenge N = 3 und k = 2 Abbildung 28

Beispiel:

Das treffendste Beispiel ist unser Dezimalsystem. Wie viele dreistellige Zahlen gibt es?

Lösung:

V = 103 = 1000, nämlich 000 bis 999.

Fakultät und Binomialkoeffizient

Bisher wurde der Term x! („x Fakultät“) ohne weitere Erläuterung verwendet. Daher sei zunächst festgestellt, dass x! nur für alle x∈ℕ definiert ist.

In bestimmten Fällen tritt aber auch 0! auf, dann gilt:

\( 0! = 1 \) Gl. 79

Ein solcher Fall tritt bei den sog. Binomialkoeffizienten auf:

Die Berechnungsvorschrift für die Kombination ohne Wiederholung (Gl. 75)

\( \frac{ {n!} }{ {(n - k)! \cdot k!} } = \left( {\begin{array}{*{20}{c} }n\\k\end{array} } \right) = \left( {\begin{array}{*{20}{c} }n\\{n - k}\end{array} } \right) \) „lies: n über k“ Gl. 80

wird auch als Binomialkoeffizient bezeichnet, wobei n, k ∈ ℕ und k ≤ n. Der Name kommt daher, dass eine Anwendung der Kombination ohne Wiederholung die Berechnung der Faktoren von Binomen beliebiger Potenz zum Gegenstand hat.

So werden die n+1 Faktoren bei der Auflösung binomischer Formeln

\( {\left( {a + b} \right)^n} \) Gl. 81

in bekannter Weise nach dem PASCALschen (Blaise PASCAL, 1623 - 1662) Dreieck

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

usw. berechnet.

Gl. 81 würde also bei n = 4 folgendermaßen aufgelöst werden:

\( {\left( {a + b} \right)^n} = 1 \cdot {a^4} + 4 \cdot {a^3}b + 6 \cdot {a^2}{b^2} + 4 \cdot a{b^3} + 1 \cdot {b^4} \)

Nun ist das PASCALsche Dreieck ein eingängiges Schema, aber insbesondere bei großen n nur schwer zu handhaben. Mit den Mitteln der Kombinatorik kann das gleiche Resultat erhalten werden. Eine Analyse obiger Gleichung zeigt, dass der Faktor a k-mal und der Faktor b (n-k)-mal. Dies weist darauf hin, dass das Produkt

\( {a^k} · {b^{n - k} } \qquad \frac{ {n!} }{ {(n - k)! \cdot k!} } \text{-mal} \) Gl. 82

auftritt.

Damit können unter Zuhilfenahme von Gl. 80 die einzelnen Summanden wie folgt berechnet werden:

\( {\left( {a + b} \right)^n} = \left( {\begin{array}{*{20}{c} }4\\0\end{array} } \right) \cdot {a^4} + \left( {\begin{array}{*{20}{c} }4\\1\end{array} } \right) \cdot {a^3}b + \left( {\begin{array}{*{20}{c} }4\\2\end{array} } \right) \cdot {a^2}{b^2} + \left( {\begin{array}{*{20}{c} }4\\3\end{array} } \right) \cdot a{b^3} + \left( {\begin{array}{*{20}{c} }4\\4\end{array} } \right) \cdot {b^4} \) Gl. 83

  Schreib uns deine Hinweise