Es gibt in der Wahrscheinlichkeitsrechnung zwei Experimenttypen, die einem immer wieder begegnen. Das sind einerseits Laplace-Experimente (alle Ereignisse sind gleich wahrscheinlich) und auf der anderen Seite Bernoulli- Experimente (genau zwei Elemente in der Ergebnismenge).
In diesem Kapitel befassen wir uns nun, welche Bedeutung die Reihenfolge der Elemente für die Wahrscheinlichkeit eines Gesamtergebnisses hat. Mit dieser Thematik befasst sich die Kombinatorik, also wie sich die Anordnung bzw. Wahrscheinlichkeit von Elementen sich ändert, wenn die Reihenfolge berücksichtigt wird.
Wie eingangs erwähnt, müssen in der Stochastik bzw. der sogenannten Kombinatorik die Anzahl der Möglichkeiten berechnet werden, bestimmte Elemente in einer Reihenfolge zu ordnen. Diese Anordnung von Elementen in einer bestimmten Reihenfolge wird in der Kombinatorik als Permutation bezeichnet. Dabei unterscheidet man zwei Arten von Permutationen, sind die Elemente unterscheidbar (ohne Wiederholung) oder sind die Elemente nicht unterscheidbar, d.h. ein Element kann in der Anordnung mehrfach vorkommen (mit Wiederholung).
Zur Wiederholung: In einem anderen Kapitel haben wir uns mit der Variation befasst, im Unterschied zur Variation werden alle Elemente ausgewählt (n-Elemente und n-Auswahlen bei der Permutation bzw. n-Elemente und k-Auswahlen bei der Variation)
Um die Permutation anschaulich darzustellen, beginnen wir mit einem Experiment: Wir haben vier Kugeln. Auf wie viele verschiedene Arten lassen sich die schwarze, rote, blaue und weißer Kugel in einer Reihe hintereinander legen?
Wir haben in diesem Fall ein Experiment, indem jedes Element (bzw. Kugel) nur einmal vorkommen darf. Zu Beginn haben wir 4 Kugeln vorliegen, daher kann man an erster Stelle (in der Reihe) 4 Kugeln auslegen. Wir haben also 4 Möglichkeiten, die erste Stelle zu besetzen. Für die zweite Position in der Reihe haben wir nur noch 3 Kugeln zur Verfügung. Wir haben also nur noch 3 Möglichkeiten, die zweite Stelle zu besetzen. Für die dritte Position haben wir noch 2 Kugeln zur Verfügung (als noch 2 Möglichkeiten). Für die vierte Position in der Reihe haben wir nur noch 1 Kugel übrig, also auch nur noch 1 Möglichkeit, eine Kugel auszulegen.
Nun müssen wir nur noch die Gesamtanzahl bestimmen: an erster Stelle haben wir 4 Möglichkeiten, an zweiter Stelle 3, an zweiter Stelle 2, an dritter Stelle 1 Möglichkeit, ergibt zusammen: 4 · 3 · 2 · 1 = 24 Möglichkeiten.
Nun wollen wir uns die Formel für die Möglichkeiten bei einer Aneinanderreihung von n-Permutationen ermitteln:
Wie im Beispiel der Kugeln gezeigt, gibt es bei der ersten Stelle n Möglichkeiten (aus n Elementen), da noch kein Element verwendet wurden. Nachdem die erste Stelle in der Anordnung der Ereignisse besetzt ist, bleiben noch (n-1) Elemente übrig, die für die zweite Stelle verwendet werden können. Also haben wir an zweiter Stelle der Anordnung noch (n – 1) Möglichkeiten ein Element zu positionieren.
Damit erhalten wir bei n-Permutationen (Anordnungen mit Berücksichtigung der Reihenfolge und ohne Wiederholung der Elemente) folgende Möglichkeiten der Anordnung der Elemente:
Möglichkeiten = n · (n -1) · (n – 2) · (n – 3) · …. ·1 = n!
Manchmal liegen auch Permutationen vor, bei denen die Elemente teilweise oder gar nicht unterscheidbar sind oder das grundsätzlich bei den Experimenten Wiederholungen zulässig sind. Auch in diesem Fall können wir die Anzahl der Möglichkeiten berechnen, die Elemente in einer Reihenfolge ohne Wiederholung zu verwenden:
Ohne eine lange Herleitung: Sind k Elemente von den insgesamt n Elementen nicht unterscheidbar, so muss diese in der Anzahl der Möglichkeiten berücksichtigt werden. Daher muss die obige Formel “Permutationen bei unterscheidbaren Elementen” noch durch die Anzahl der nicht unterscheidbaren Elementen geteilt werden. Als Formel für die Permutation von n Elementen mit k Elementen, die nicht unterscheidbar sind, gilt:
Möglichkeiten = n! : k!
Beispiel:
Wir haben zwei grüne Kugeln (g) und eine rote Kugel (r). Wie viele Möglichkeiten gibt es, diese auszulegen (in Reihenfolge)?
Die Kombinatorik befasst sich mit der Anzahl von Anordnung von einer bestimmten Anzahl an Elementen mit oder ohne Berücksichtigung der Reihenfolge. Sind die Elemente unterscheidbar (und kommen diese nur einzeln vor) so spricht man von “ohne Wiederholung”. Sind die Elemente hingegen nicht unterscheidbar, so spricht man von “mit Wiederholung”, da jedes Element, dass bereits verwendet wurde, wieder verwendet werden kann.
Permutation bezieht sich auf die Anordnung von Objekten in einer bestimmten Reihenfolge, ohne sich zu wiederholen.
Es gibt n! (n Fakultät) verschiedene Permutationen für eine Menge von n Elementen.
Bei einer Permutation ohne Wiederholung wird jedes Element nur einmal verwendet. Bei einer Permutation mit Wiederholung kann ein Element mehrmals in verschiedenen Positionen erscheinen.
Da es keine sich wiederholenden Buchstaben gibt, verwenden wir die Formel der Permutation ohne Wiederholung n!. Es gibt also 6! = 720 verschiedene Permutationen.
Da es sich wiederholende Buchstaben gibt (2 Es und 2 Ls), verwenden wir die Formel für die Permutation mit Wiederholung: n! / (p1! * p2! * … * pk!), wo p die Anzahl der Wiederholung jeden Buchstaben ist. So gibt es 6! / (2! * 2!) = 180 verschiedene Permutationen.
Die Formel für die Permutation von n Elementen aus einer Menge von r Elementen ist P(n, r) = n! / (n-r)!.
Da die Reihenfolge wichtig ist, verwenden wir die Formel P(n, r). Es gibt also P(10, 3) = 720 verschiedene Möglichkeiten, die Bücher zu arrangieren.
Da die Buchstaben beliebig oft verwendet werden können, gibt es 5^5 = 3125 verschiedene Anordnungen.
Da jeder Buchstabe die gleiche Chance hat, an erster Stelle zu stehen, beträgt die Wahrscheinlichkeit 1/5 oder 20%.
Da es sich wiederholende Buchstaben gibt (5 As und 5 Bs), verwenden wir die Formel für die Permutation mit Wiederholung: n! / (p1! * p2! * … * pk!), so gibt es 10! / (5! * 5!) = 252 verschiedene Permutationen.