Kombinatorik

Einleitung
Wir haben im letzten Abschnitt die Frage offen gelassen, wie man im Einzelfall die Anzahl der Elementarereignisse findet und wie man die abstrakte Zuordnung der Elementarereignisses auf eine mathematische Formel realisiert. Wir wollen die Problematik zunächst an einem Beispiel erläutern.

Im Zahlenlotte ,,6 aus 49'' werden nacheinander 6 Kugeln aus einem Behälter mit 49 durchnumerierten Kugeln gezogen. Hierbei muß man bei der Definition des Elementarereignisses aufpassen. Es wäre falsch anzunehmen, daß das einmalige Ziehen einer Kugel ein Elementarereignis wäre und das Ereignis A= ,,6 aus 49'' dann aus 6 Elementarereignissen gebildet werden könnte. Dieser Ansatz wäre nur dann korrekt, wenn jede Kugel nach dem Ziehen wieder in den Behälter zurückgelegt und durch Mischen der Kugeln der gleiche Bedingungskomplex wie beim ersten Zug wiederhergestellt werden würde. Wenn die Kugel dagegen nicht zurückgelegt wird, wie es beim Zahlenlotto auch tatsächlich der Fall ist, hat man bei jedem folgenden Zug jeweils eine Kugel weniger im Behälter und damit einen veränderten Bedingungskomplex. Elementarereignisse können aber nur für ein und denselben Bedingungskomplex definiert werden. Der einzig richtige Ansatz ist in diesem Versuch, das sechsmalige Ziehen einer Kugel als Elementarereignis zu definieren. Auf die Reihenfolge der gezogenen Zahlen kommt es hierbei nicht an. Die Zahlen werden am Ende der Ziehung in aufsteigender Reihenfolge sortiert. Die Anzahl der Elementarereignisse findet man mit Hilfe der Kombinatorik (siehe später in diesem Abschnitt) zu

$$n=\frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44} {1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6} = 13983816$$

und die abstrakte Definition der Elementarereignisse lautet: Die Elementarereignisse beim Lotto ,,6 aus 49'' bestehen aus allen Kombinationen von 6 Zahlen

$$E_{\nu_{1} \nu_{2}.....\nu_{6}} = (\nu_{1},\nu_{2},...,\nu_{6})$$

mit $0 < \nu_{k} \leq 49$ und $\nu_{i} < \nu_{k}$ für $i < k$. Verschiedene Elementarereignisse müssen sich in mindestens einer der Zahlen $\nu_{k} (k=1,2,...,6)$ unterscheiden.

In diesem Beispiel und in fast allen Anwendungen der Statistik kann man die Anzahl und Definition der Elementarereignisse mit Hilfe der 4 Grundaufgaben der Kombinatorik lösen. Im folgenden werden wir die 4 Grundaufgaben angeben und durch Beispiele erläutern. Für Beweise verweisen wir auf die einschlägige Literatur.

1.Grundaufgabe
Es seien n voneinander verschiedene Elemente gegeben. In wieviel verschiedenen Anordnungen (Permutationen) kann man dieselben in eine Reihe nebeneinander stellen, oder wenigstens gestellt denken?
Satz: Die Anzahl der Permutationen von n verschiedenen Elementen ist gleich dem Produkt

$$n! = 1 \cdot 2 \cdot 3 \cdot \cdot \cdot \cdot \cdot n$$ (1)

aller natürlichen Zahlen von 1 bis n.

Ein typisches Beispiel ist die Gruppenaufnahme. Ein Fotograf soll n verschiedene Personen, die in einer Reihe stehen, fotografieren. Die Personen können sich nicht einigen, wer neben wem steht. Der Fotograf macht daher den Vorschlag, Aufnahmen von allen nur denkbaren Anordnungen zu machen. Jeder kann sich dann hinterher die ihm genehme Anordnung aussuchen. Dieser Fotograf hat seinen Vorschlag ohne Kenntnis der Kombinatorik gemacht. Wie man aus Formel (1) ersieht, würde sein Film mit 24 Bildern bei einer Familie mit 4 Personen gerade noch ausreichen. Dagegen müßte er bei einer Fußballmanschaft praktisch schon die gesamte Jahresproduktion der deutschen Filmindustrie aufkaufen.

Eine Permutation stellt man mathematisch dadurch da, daß man die geänderte Reihe unter die originale Reihe schreibt, z.B.

$$P = \left( \begin{array}{cccc} a_{1} & a_{2} & a_{3} & a_{4} \\ a_{2} & a_{3} & a_{1} & a_{4} \end{array} \right)$$

Man spricht von einer geraden Permutation, wenn sich die geänderte Reihe aus einer geraden Anzahl von Vertauschungen nebeneinander stehender Elemente ergibt, sonst von einer ungeraden Permutation.

2.Grundaufgabe
Es seien n Elemente gegeben, welche nicht alle voneinander verschieden sind, sondern so in p Arten, $1 \leq p \leq n$, zerfallen, daß die Elemente jeder einzelnen Art einander gleich, jedoch Elemente verschiedener Art verschieden sind. Die erste dieser Arten enthalte $\nu_{1}$, die zweite $\nu_{2}$, ..., die letzte $\nu_{p}$ Elemente. Wie groß ist unter diesen Voraussetzungen die Anzahl der Permutationen?
Satz: Die Anzahl der Permutationen in der 2. Grundaufgabe der Kombinatorik ist durch

$$\frac{n!}{\nu_{1}! \nu_{2}! .... \nu_{p}!} = \frac{(\nu_{1}+\nu_{2}+....+\nu_{p})!}{\nu_{1}! \nu_{2}! .... \nu_{p}!}$$ (2)

gegeben.

Wir greifen noch einmal das Beispiel der 1. Grundaufgabe auf, verändern es aber dahingehend, daß die Gruppe aus m Männern und f Frauen besteht. Die Männer und Frauen untereinander haben sich bereits darauf geeinigt, sich der Größe nach aufzustellen. Zwischen den Männern untereinander und den Frauen untereinander braucht der Fotograf also nicht mehr zu unterscheiden. Falls es sich hierbei um die Bonner Bundesregierung mit 12 männlichen und 3 weiblichen Ministern handeln sollte, hätte der Fotograf die Wahl zwischen 455 verschiedenen Möglichkeiten.

3.Grundaufgabe
Wenn n Elemente gegeben sind und k eine natürliche, nicht oberhalb n gelegene Zahl bezeichnet, so nennt man jede Zusammenstellung, die man erhält, wenn man irgendwelche k der gegebenen Elemente herausgreift und in irgendeine Anordnung nebeneinander stellt, eine Kombination k-ter Ordnung der gegebenen Elemente. Wenn zwei Kombinationen, welche die gleichen Elemente in verschiedener Anordnung enthalten, als verschieden gelten sollen, so spricht man von Kombinationen mit Berücksichtigung der Anordnung, sonst von Kombinationen ohne Berücksichtigung der Anordnung. Sind die gegebenen Elemente untereinander verschieden, sodaß auch in den von ihnen gebildeten Kombinationen nur verschiedene Elemente auftreten, so spricht man von Kombinationen ohne Widerholung (oder auch Variationen). Man soll also, wenn n eine beliebige und k eine nicht oberhalb von n gelegene natürliche Zahl bedeutet, die Anzahl der Kombinationen k-ter Ordnung von n voneinander verschiedenen Elementen ermitteln, und zwar 1.) mit Berücksichtigung der Anordnung und 2.) ohne Berücksichtigung der Anordnung.
Satz: Unter den gemachten Voraussetzungen der 3. Grundaufgabe ist die Anzahl der Kombinationen mit Berücksichtigung der Anordnung durch das Produkt

$$n(n-1)(n-2) ...... (n-k+1),$$ (3)

sowie ohne Berücksichtigung der Anordnung durch den Ausdruck

$$\frac{n(n-1)(n-2).....(n-k+1)}{1 \cdot 2 \cdot 3 \cdot \cdot \cdot k} = \left(\begin{array}{c} n \\ k \end{array} \right)$$ (4)

gegeben.

Wir greifen noch einmal das Lottospiel ,,6 aus 49'' auf. Da die Reihenfolge der Zahlen hierbei keine Rolle spielt, erhalten wir tatsächlich die bereits oben angegebene Anzahl von Spielmöglichkeiten. Würde die Reihenfolge eine Rolle spielen, so würde sich die Zahl der verschiedenen Spiele auf $\approx 10^{10}$ erhöhen. Wir haben in diesem Beispiel stillschweigend die sogenannte Zusatzzahl ausser acht gelassen. Bei der Ziehung der Zusatzzahl spielt die Reihenfole eine Rolle, sie wird nämlich tatsächlich als letzte Zahl gezogen. Dieses Beispiel wird in den Aufgaben behandelt.

4.Grundaufgabe
Es seien n Arten von Elementen gegeben, von denen jede mehrere, und zwar wenigstens k Elemente enthält. Die Elemente jeder einzelnen Art seien einander gleich, aber Elemente verschiedener Arten seien verschieden. Dann ist es möglich, Kombinationen der gegebenen Elemente zu bilden, in welchen mehrere gleiche Elemente vorkommen, und solange man nur solche Kombinationen betrachtet, welche nicht mehr als k Elemente enthalten, ist die Anzahl der gleichen Elemente, welche in ein und dieselbe Kombination aufgenommen werden dürfen, einer Einschränkung nicht unterworfen. Es sind also n verschiedene Elemente gegeben, aber bei der Bildung von Kombinationen dieser Elemente zu je k darf jedes einzelne Element unbeschränkt oft wiederholt werden. Dieses nennt man auch kurz Kombination mit Wiederholung. Man kann sich diesen Sachverhalt auch anschaulich folgendermaßen vorstellen. Ein Drucker hat 26 Kästen mit Buchstaben, für jeden Buchstaben einen Kasten. Er soll Wörter mit k gleichen oder verschiedene Buchstaben schreiben, wobei die Anzahl der Buchstaben in jedem Kasten mindestens gleich k ist, damit die Bildung von Wörtern aus k gleichen Buchstaben überhaupt möglich ist. Gefragt ist nach der möglichen Zahl der Wörter mit k Buchstaben, die man erhält, wenn man es dem Zufall überläßt, aus welchem Kasten man einen Buchstaben entnimmt. Hierbei sehen wir natürlich jede Zusammenstellung von Buchstaben als ein Wort an. Dieses führt uns zur 4. Grundaufgabe, die folgendermaßen formuliert werden kann. Man soll die Anzahl der Kombinationen k-ter Ordnung von n verschiedenen, unbeschränkt oft wiederholbaren Elementen ermitteln, und zwar 1.) mit Berücksichtigung der Anordnung und 2.) ohne Berücksichtigung der Anordnung.
Satz: Die Anzahl der Kombinationen k-ter Ordnung von n verschiedenen, unbeschränkt oft wiederholbaren Elementen ist gegeben durch

$$n^{k}$$ (5)

mit Berücksichtigung der Anordnung und durch

$$\left( \begin{array}{c} n+k-1 \\ k \end{array} \right)$$ (6)

ohne Berücksichtigung der Anordnung.

Eine einfache Anwendung hierzu ist die folgende Aufgabe. Die Zeichen des in der Telegrafie benutzten Morse Alphabets sind aus nur zwei verschiedenen Elementen, Punkt und Strich, zusammengesetzt. Wieviel Zeichen lassen sich aus diesen Elementen bilden, wenn zur Bildung eines Zeichens nicht mehr als 5 Elemente verwendet werden dürfen. Die Antwort ist einfach. Da es hierbei auf die Reihenfolge ankommt, erhalten wir aus (5) mit n=2 und k= 1,2,3,4,5 die Lösung

$$\sum_{k=1}^{5} 2^{k} = 62$$

Wir sehen also, daß eine angeregte Unterhaltung mit Hilfe des Morse Alphabets nicht möglich ist. Ein Wortschatz von 62 Wörtern entspricht dem eines etwa 4 jährigen Kindes. In einem späteren Abschnitt werden wir noch auf eine ähnliche Anwendung eingehen, nämlich auf die Zahlendarstellungen in Digitalrechnern.

Rekursive Relationen
Häufig kommt man allerdings bei der Lösung von kombinatorischen Problemen mit den 4 Grundaufgaben alleine nicht aus. Dieses tritt im allgemeinen dann auf, wenn die Anordnungen der Elemente weiteren Einschränkungen unterworfen wird. Ein Beispiel möge dieses verdeutlichen. Gesucht ist die Anzahl $F(k)$ der möglichen Dualzahlen $D(k)$ mit $k$ Stellen. Eine Dualzahl mit $k$ Stellen ist bekanntlich durch eine Anordnung von $k$ Nullen und Einsen gegeben. Gemäß der 4. Grundaufgabe ($n=2$) ergeben sich $2^{k}$ verschiedene Zahlen. Führt man allerdings als Nebenbedingung ein, daß niemals 2 Einsen nebeneinander stehen dürfen, so wird die Anzahl der Möglichkeiten stark reduziert. Für $k=1$ erfüllen die Dualzahlen 0 und 1 die Bedingung, also ist $F(1)=2$. Für $k=2$ erfüllen nur 00, 01 und 10 die Nebenbedingung, also $F(2)=3$. Entsprechend ist $F(3)=4$ und $F(4)=8$. Der allgemeine Schluß von $F(k)$ auf $F(k+1)$ geht wie folgt. Wenn $D(k+1)$ in der letzten Stelle eine Null hat, so sind auch alle $F(k)$ Zahlenkombinationen in den vorhergehenden Stellen erlaubte Kombinationen für $D(k+1)$. Hat $D(k+1)$ umgekehrt in der letzten Stelle eine Eins, so darf in der vorhergehenden Stelle keine Eins auftreten. Erlaubte Kombinationen sind nur die $F(k-1)$ Kombinationen für die $k-1$ Stellen der Dualzahl $D(k-1)$. Zusammengefaßt ergibt sich

$$F(k+1) = F(k) + F(k-1).$$

Dieses ist die berühmte Fibonacci- Zahlenfolge, die uns später noch einmal ausgiebig beschäftigen wird. Ähnliche Rekursiv- Relationen können in vielen Fällen zur Lösung kombinatorischer Probleme hergeleitet werden.
Übungen
Aufgabe 1:
Beim Skat werden an drei Mitspieler je 10 Karten vergeben, 2 Karten wandern in den sogenannten Topf. Der Wert jeder der 32 Karten ist verschieden. Wieviele verschiedene Spielmöglichkeiten gibt es ?
Aufgabe 2:
Abweichend von den Erläuterungen im Text werden beim Zahlenlotto '6 aus 49' zunächst 6 Zahlen zufällig gezogen, wobei für einen Gewinn nicht auf die Reihenfolge der gezogenen Zahlen ankommt. Zusätzlich aber wird am Schluß der Ziehung eine sogenannte Zusatzzahl ermittelt. Gewonnen hat, wer mindestens 3 der ersten 6 Ziehungen richtig vorhergesagt hat. Wer 5 Zahlen aus den ersten 6 und zusätzlich die Zusatzzahl richtig getippt hat, hat ebenfalls gewonnen. Ein höherer Gewinn schließt alle niedrigeren Gewinne aus.
a) Wieviele Gewinnmöglichkeiten gibt es insgesamt ?
b) Wieviele Gewinnmöglichkeiten gibt es für die Gewinnklasse '5 + Zusatzzahl' ?
c) Im folgenden Applet können Sie Ihre Chancen im Lotteriespiel prüfen. Zunächst müssen Sie 6 aus 49 Zahlen ankreuzen. Dazu drücken Sie den Button Schein und füllen den Lottoschein aus. Anschliessend drücken Sie auf Start. Bei jedem Spiel setzen Sie 1 Euro. Einsatz, Gewinn und Differenz aus Gewinn und Einsatz wird im rechten Fenster oben links angezeigt. Ausserdem wird der effektive Gewinn als fortlaufende Kurve dargestellt. Solange die Kurve rot ist, ist Ihr Einsatz höher als der Gewinn, erst bei blauer Kurve ist Ihr effektiver Gewinn positiv. Die Gewinnquoten der einzelnen Klassen werden auf der rechten Seite des Fensters angezeigt und können mit den Schiebern ganz rechts im Applet verändert werden. Und hier liegt ja bekanntlich das Geheimnis des realen Lottospiels. Die 6 Zahlen werden mit Sicherheit zufällig gewürfelt, die Gewinnquoten sind allerdings nicht zufällig. Sie richten sich danach, wieviele andere Spieler die Gewinnzahlen richtig vorhergesagt haben. Sie haben also keinen Einfluss auf die Gewinnzahlen, aber Einfluss auf die Gewinnquoten. Beobachten Sie selbst, wie Ihr Konto nach einigen Jahren aussieht.
Aufgabe 3:
Sieben Mädchen tanzen in einem Kreis. In wievielen verschiedenen Möglichkeiten können sie den Kreis bilden ?
Aufgabe 4:
Wieviele verschiedene 4-stellige Zahlen kann man aus den Ziffern 0, 1, 2, 3, 4, 5 und 6 bilden? Keine Zahl darf mit einer Null beginnen.