Kombinatorik

1 Einleitung

Als äußerst hilfreich zur Berechnung von Wahrscheinlichkeiten ist es, gewisse Abzählmethoden zu beherrschen. Dabei stellt sich immer wieder die Frage: "Wieviele Möglichkeiten gibt es?"
Auf wieviel verschiedene Weisen kann ich drei Leute im Flugzeug nebeneinander setzen? Wieviele mögliche Ziehungen gibt es bei den Lottozahlen?
Es ist leicht ersichtlich, dass uns die Beantwortung dieser Fragen stark bei Wahrscheinlichkeitsproblemen weiterhilft, nämlich Fragen nach der Wahrscheinlichkeit im Flugzeug am Fenster zu sitzen oder der Wahrscheinlichkeit, im Lotto zu gewinnen.

2 Fakultäten

Bei der ersten der beiden Fragen ist es wichtig, in welcher Reihenfolge man sich platziert.
Angenommen es gibt drei Personen (A,B,C), die im Flugzeug in der gleichen Reihe sitzen. Dann bekommt eine Person den Fensterplatz, eine den Mittelplatz und eine Person sitzt am Gang. Wie hoch ist nun aber die Wahrscheinlichkeit, dass Person A am Fenster sitzt?
(Man muss zugeben, dass sich die konkrete Frage auch einfacher beantworten lässt, sich aber das mathematische Prinzip mit der folgenden Analyse gut veranschaulichen lässt.)
Dazu müssen wir ermitteln, wie viele Möglichkeiten es gibt, die drei Personen auf die drei Plätz zu verteilen. (Die verschiedenen Reihenfolgen gleicher Objekte nennt man Permutationen.) Wir suchen also nach der Anzahl aller Permutationen von drei Objekten. Da es sich um eine ziemlich geringe Zahl handelt, könnten wir einfach alle Kombinationen auflisten und dann abzählen. Also zum Beispiel: Person A sitzt am Fenster, Person B in der Mitte und Person C am Gang, u.s.w. Da wir das Ergebnis aber auf beliebig große Mengen von Objekten verallgemeinern wollen, versuchen wir ein systematisches Prinzip zu finden.
Das ist auch gar nicht so schwer. Wir überlegen einfach, wie viele mögliche Personen am Fenser sitzen können. Das sind drei. Nun überlegen wir, wieviele Möglichkeiten es für den Mittelplatz gibt. Da eine Person bereits einen Platz hat, bleiben nur noch zwei Möglichkeiten. Für den letzten Platz bleibt dann schließlich nur noch eine Person. Es gibt also insgesamt 3*2*1 = 6 Möglichkeiten, die drei Plätze zu belegen, also sechs Permutationen von drei verschiedenen Objekten.
Analog hätten wir bei fünf Plätzen 5*4*3*2*1 = 120 Möglichkeiten erhalten.
Für n Plätze hätten wir n*(n-1)*...*2*1 Möglichkeiten erhalten.
Dieses Produkt nennt man die Fakultät von n, und man schreibt n*(n-1)*...*2*1 = n! dafür.

Nach diesen Überlegungen lässt sich nun auch unsere Frage beantworten, wie hoch die Wahrscheinlichkeit ist, dass Person A am Fenster sitzt.
Es gibt insgesamt 3! viele Möglichkeiten, die Personen auf die Plätze zu verteilen. Da wir nur daran interessiert sind, ob Person A am Fenster sitzt, müssen wir noch beachten, dass es uns egal ist wie sich die anderen beiden auf die übrigen Plätze verteilen. Es gibt somit mehrere Varianten der Sitzverteilung, in denen Person A am Fenster sitzt, und zwar genau so viele, wie es Möglichkeiten gibt, die anderen beiden Personen auf die beiden übrigen Plätze zu verteilen. Mit dem gleichen Argument wie oben sind das geanu 2! verschiedene Möglichkeiten.
Da es insgesamt 3! = 6 Varianten gibt, die alle gleich wahrscheinlich sind, d.h. alle mit der Wahrscheinlichkeit 1/6 eintreten werden und 2! = 2 davon zu unserem gewünschten Ergebnis führen, haben wir insgesamt eine Wahrscheinlichkeit von 2!/3! = 2/6 = 1/3 = 33,33%, dass Person A am Fenster sitzen wird.

3 Binomialkoeffizienten

Der Fall mit den Lottozahlen liegt noch etwas anders.
Wir überlegen uns zunächst, wie viele Möglichkeiten es gibt, sechs Zahlen aus 49 zu ziehen. Dabei verfahren wir nach dem gleichen Prinzip wie eben. Für die erste gezogene Zahl gibt es 49 Möglichkeiten, für die zweite noch 48, da eine ja bereits entfernt wurde, für die dritte 47, u.s.w. Insgesamt gibt es also 49*48*47*46*45*44 = 10.068.347.520, also über 10 Milliarden Möglichkeiten.
Nun ist es beim Lotto aber bekanntlich egal, in welcher Reihenfolge diese Zahlen gezogen werden, d.h. wir müssen uns überlegen, wieviele mögliche Ziehungen jeweils das gleiche Ergebnis liefern. Da es sich um sechs gezogene Zahlen handelt, wissen wir aus den obigen Überlegungen, dass dies genau die Anzahl der Permutationen von sechs verschiedenen Elementen entspricht, und diese Anzahl ist, wie ebenfalls oben gesehen 6! = 720.
Jeweils 720 verschiedene Ziehung bedeuten für die Lottospieler das gleiche Ergebnis. An wirklichen Ergebnissen gibt es also nicht gut 10 Milliarden, sondern nur 10.068.347.520/720 = 13.983.816, d.h. etwa 14 Millionen, was aber weiterhin genügend viele Möglichkeiten sind, um denjenigen, der sich mit der Kombinatorik auskennt, eigentlich davon abzuhalten, Lotto zu spielen.
Die Wahrscheinlichkeit für sechs Richtige im Lotto ist also ungefähr 1 zu 14 Millionen, was etwa 0,000007% entspricht.

Zurück zur mathematischen Theorie. Was wir hier gesehen haben, ist, dass es 13.983.816 verschiedene Möglichkeiten gibt, 6 aus 49 auszuwählen, wenn uns dabei die Reihenfolge, in der wir auswählen, nicht interessiert. Berechnet hat sich diese Zahl durch 49*48*47*46*45*44 / 6*5*4*3*2*1. Mit unser oben eingeführten Fakultätsschreibweise schreibt sich dies als 49!/(49-6)!*6!.
Allgemein ausgedrückt:
Die Anzahl der Möglichkeiten, k Objekte aus n verschiedenen Objekten auszuwählen, wobei die Reihenfolge unwichtig ist, beträgt n! / k!*(n-k)! und nennt sich Binomialkoeffizient "n über k". Man schreibt:

Bekannt sind diese Binomialkoeffizienten unter anderem aus den Binomischen Formeln.

Mit diesen Hilfsmitteln lassen sich jetzt natürlich auch andere Fragen lösen. Es wäre ja auch interessant zu wissen, wie hoch die Wahrscheinlichkeit ist, im Lotto fünf Richtige zu haben.
Wir wir wissen bereits, dass es verschiedene Ziehungen gibt.
Wenn wir jetzt nur nach fünf Richtigen suchen, so müssen wir uns überlegen, wie viele Möglichkeiten es gibt fünf Richtige bei sechs gezogenen Zahlen zu haben. Zunächst dürfen also unsere fünf Zahlen beliebig auf die sechs gezogenen verteilt werden, d.h. Möglichkeiten. Hinzu kommt, dass die sechste Zahl eine aus den 43 nicht von uns getippten Zahlen sein muss, wofür es Möglichkeiten gibt.
Insgesamt ist unsere Chance fünf Richtge zu haben also * / = 6*43 / 13.983.816 = 0,000018..., d.h. etwa 0,0018%.