Anzahl kombinationen kleiner gleich k

Diese Seite enth�lt eine Reihe von konkreten Beispielen aus dem Bereich der Kombinatorik und Wahrscheinlichkeitsrechnung.
F�r viele Beispiele ben�tigt man nur die Kenntnis der elementaren Stochastik-Formeln f�r Permutationen, Kombinationen und Variationen.

Permutationen, Kombinationen und Variationen

Permutationen ohne und mit Wiederholung (Anzahl der Reihenfolgen f�r eine bestimmte Ziehung)

Anzahl der M�glichkeiten bei n verschiedenen Kugeln (Permutationen ohne Wiederholung):

Pn = n!

Herleitung: Bei den Permutationen ohne Wiederholung hat man f�r die erste Kugel noch n M�glichkeiten. F�r die zweite Kugel gibt es nur noch n�1 M�glichkeiten, weil eine Kugel schon platziert
wurde. Das sind dann zusammen n � (n�1) M�glichkeiten. Wenn man alle n Kugeln platziert, dann ergeben sich schlie�lich n � (n�1) � (n�2) � (n�3) � ... � 1 = n! m�gliche Reihenfolgen.

Anzahl der M�glichkeiten bei n Kugeln mit n1 Kugeln vom Typ 1, n2 Kugeln vom Typ 2, ... und nk Kugeln vom Typ k und n = n1 + n2 + ... + nk (Permutationen mit Wiederholung):

Pn = n! / (n1! · n2! ·...· nk!)

Anzahl der M�glichkeiten bei der Ziehung von k Kugeln (ohne Zur�cklegen) bei n unterscheidbaren Kugeln:

Cn,k = (nk) = n! / (k!·(n�k)!)

Herleitung: Da bei den Kombinationen ohne Wiederholung die Reihenfolge keine Rolle spielt, muss man die Anzahl der Variationen ohne Wiederholung (hier wird die Reihenfolge ber�cksichtigt)
durch die Anzahl der verschiedenen Reihenfolgen (Permutationen) teilen. F�r die Anzahl der Kombinationen gibt es deshalb (n!/(n�k)!) / k! = n! / (k!�(n�k)!) = (nk) M�glichkeiten.

Anzahl der M�glichkeiten bei der Ziehung von k Kugeln (mit Zur�cklegen) bei n unterscheidbaren Kugeln:

Cn,k = (n�1+kk) = (n�1+k)! / (k!·(n�1)!)

Herleitung: Da die Reihenfolge bei Kombinationen mit Wiederholung keine Rolle spielt, kann man die k gezogenen Kugeln z.B. nach der Gr��e der aufgedruckten Zahl ordnen.
Angenommen, man w�rde k = 5 Kugeln von insgesamt n = 6 Kugeln ziehen. Ein Beispiel w�re 23366. Die gezogenen Kugeln hatten also die aufgedruckten Zahlen 2, 3 und 6.
Wenn man alle Zahlen mit x bezeichnet, k�nnte man dieses Ziehungsbeispiel auch so schreiben: /x/xx///xx.
Dabei stehen vor dem ersten Schr�gstrich die Einsen (hier keine Einsen), zwischen dem ersten und zweiten Schr�gstrich die Zweien (hier eine Zwei),
zwischen dem zweiten und dritten Schr�gstrich die Dreien (hier zwei Dreien), zwischen dem dritten und vierten Schr�gstrich die Vieren (hier keine Vier),
zwischen dem vierten und f�nften Schr�gstrich die F�nfen (hier keine F�nf) und nach dem f�nften Schr�gstrich die Sechsen (hier zwei Sechsen).
Wegen der 5 gezogenen Kugeln kommt also das x immer genau k = 5 mal vor. Und um die n = 6 m�glichen Zahlen voneinander abtrennen zu k�nnen, braucht man immer genau n�1 = 5 Schr�gstriche.
Jeder Zahlenkombination ist also eine andere Reihenfolge (Permutation) von x-en und Schr�gstrichen eineindeutig zugeordnet.
Und f�r die Anzahl der m�glichen Permutationen (mit Wiederholung) von genau k x-en und n�1 Schr�gstrichen (also von insgesamt n�1+k = 10 Zeichen)
und damit auch der m�glichen Zahlenkombinationen (mit Wiederholung) von k aus n unterscheidbaren Kugeln gibt es (n�1+k)! / (k!�(n�1)!) = (n�1+kk) M�glichkeiten.

Anzahl der M�glichkeiten bei der Ziehung von k Kugeln (ohne Zur�cklegen) bei n unterscheidbaren Kugeln:

Vn,k = (nk) · k! = n! / (n�k)!

Herleitung: Wenn man die erste Kugel zieht, dann gibt es daf�r n M�glichkeiten. F�r die zweite Kugel gibt es nur noch n�1 M�glichkeiten, weil die erste Kugel ja nicht wieder zur�ckgelegt wurde.
Das sind dann zusammen n � (n�1) M�glichkeiten. Wenn man k Kugeln zieht, dann ergeben sich schlie�lich n � (n�1) � (n�2) � (n�3) � ... � (n�k+1) = n! / (n�k)! M�glichkeiten.

Anzahl der M�glichkeiten bei der Ziehung von k Kugeln (mit Zur�cklegen) bei n unterscheidbaren Kugeln:

Vn,k = nk

Herleitung: Wenn man die erste Kugel zieht, gibt es daf�r n M�glichkeiten. F�r die zweite Kugel gibt es wieder n M�glichkeiten, weil die erste Kugel ja wieder zur�ckgelegt wurde.
Das sind dann zusammen n � n = n2 M�glichkeiten. Wenn man k Kugeln zieht, dann ergeben sich schlie�lich nk M�glichkeiten.

Bemerkung: Das Ziehen von k Kugeln (mit Zur�cklegen der jeweils gezogenen Kugel) bei n unterscheidbaren Kugeln entspricht dem k-fachen W�rfeln
mit einem �W�rfel� mit n unterscheidbaren gleichen Fl�chen.

H�ufige Fehlerquellen bei Stochastik-�berlegungen (Beispiele):

Wie viele M�glichkeiten gibt es, k=6 Kugeln von n=49 unterscheidbaren Kugeln zu ziehen, wenn die Kugeln nicht zur�ckgelegt werden und die Reihenfolge keine Rolle spielt (Lotto 6 aus 49)?

F�r die Zahl der M�glichkeiten, die alle gleichwahrscheinlich sind, gilt:

Nn,k = (nk) = n! / (k!·(n�k)!) (Kombinationen ohne Wiederholung)
N49,6 = 49! / (6!·43!) = (49! / 43!) / 6! = 49 · 48 · 47 · 46 · 45 · 44 / (1 · 2 · 3 · 4 · 5 · 6) = 13.983.816

Die Wahrscheinlichkeit f�r das Auftreten einer bestimmten dieser Kombinationen und damit die Wahrscheinlichkeit f�r 6 Richtige im Lotto ist dann also:

Pn,k = 1 / Nn,k = 1/13.983.816

Herleitung:
Die Wahrscheinlichkeit, dass die erste gezogene Kugel richtig ist, betr�gt 6/49.
Die Wahrscheinlichkeit, dass auch die zweite gezogene Kugel richtig ist, betr�gt 5/48.
Die Wahrscheinlichkeit, dass auch die dritte gezogene Kugel richtig ist, betr�gt 4/47.
Die Wahrscheinlichkeit, dass alle 6 gezogenen Kugeln richtig sind, betr�gt dann 6/49 · 5/48 · 4/47 · 3/46 · 2/45 · 1/44 = 1/13.983.816.

Die Wahrscheinlichkeit, zu den 6 richtigen Lottozahlen auch noch die Superzahl richtig zu haben, ist zehnmal so klein (wegen der zehn M�glichkeiten f�r die Superzahl: 0, 1, 2, ... , 9) und betr�gt nur 1 : 139.838.160.

Beispiele f�r andere Lotto-Ziehungsarten:

0 aus 49: N49,0 = 1
1 aus 49: N49,1 = 49
2 aus 49: N49,2 = 1176
3 aus 49: N49,3 = 18.424
4 aus 49: N49,4 = 211.876
5 aus 49: N49,5 = 1.906.884
6 aus 49: N49,6 = 13.983.816
7 aus 49: N49,7 = 85.900.584
8 aus 49: N49,8 = 450.978.066

Bei Lotto 24 aus 49 und Lotto 25 aus 49 ist die Zahl der M�glichkeiten am gr��ten.
Danach nimmt sie in gleicher Weise wieder ab, wie sie zugenommen hat.
Lotto 6 aus 49 hat deshalb genau so viele M�glichkeiten wie Lotto 43 aus 49.

Weitere Berechnungen zu Wahrscheinlichkeiten beim Lotto findet man auf der Lotto-Seite.

Beispiel 2 (Kombinationen beim W�rfeln)

Wie viele M�glichkeiten gibt es bei k=3 maligem W�rfeln mit einem W�rfel mit n=6 unterscheidbaren Fl�chen, wenn die Reihenfolge keine Rolle spielt?
Das entspricht der Ziehung von k=3 Kugeln bei n=6 unterscheidbaren Kugeln, wenn die Kugeln jedes Mal zur�ckgelegt werden und die Reihenfolge auch hier keine Rolle spielt.

F�r die Zahl der M�glichkeiten gilt (Die M�glichkeiten sind nicht gleichwahrscheinlich!):

Nn,k = (n�1+k)! / (k!·(n�1)!) (Kombinationen mit Wiederholung)
N6,3 = (6�1+3)! / (3!·(6�1)!) = 8! / (3!·5!) = 56

Es gibt 6 M�glichkeiten, bei denen 3 gleiche Fl�chen vorkommen. Die Wahrscheinlichkeit ist jeweils 1/216.
Es gibt 30 M�glichkeiten, bei denen 2 gleiche Fl�chen vorkommen. Die Wahrscheinlichkeit ist jeweils 3/216.
Es gibt 20 M�glichkeiten, bei denen alle Fl�chen verschieden sind. Die Wahrscheinlichkeit ist jeweils 6/216.
( 6 · 1/216 + 30 · 3/216 + 20 · 6/216 = 1 (siehe Beispiel 4))

Weitere Beispiele:

N6,1 = 6
N6,2 = 21
N6,3 = 56
N6,4 = 126
N6,5 = 252
N6,6 = 462
N6,7 = 792
N6,8 = 1287
N6,9 = 2002
N6,10 = 3003
N6,11 = 4368
N6,12 = 6188

Beispiel 3 (Ziehungsm�glichkeiten bei Lotto 6 aus 49 mit Ziehungsreihenfolge)

Wie viele M�glichkeiten gibt es, k=6 Kugeln von n=49 unterscheidbaren Kugeln zu ziehen, wenn die Kugeln nicht zur�ckgelegt werden und die Reihenfolge wichtig ist?

F�r die Zahl der M�glichkeiten gilt (Die M�glichkeiten sind alle gleichwahrscheinlich.):

Nn,k = n! / (n�k)! (Variationen ohne Wiederholung)
N49,6 = 49! / 43! = 49 · 48 · 47 · 46 · 45 · 44 = 10.068.347.520

Herleitung:
F�r die erste Kugel gibt es 49 M�glichkeiten.
F�r die zweite Kugel gibt es 48 M�glichkeiten, weil ja nur noch 48 Kugeln vorhanden sind.
F�r die sechste Kugel gibt es schlie�lich nur noch 44 M�glichkeiten.
Die Gesamtzahl der M�glichkeiten (Variationen) ist dann das Produkt der Anzahl der einzelnen M�glichkeiten.

N�herung: N49,6 = 46,56 = 10.109.221.620 (46,5: arithmetisches Mittel der 6 Faktoren)

Beispiel 4 (Variationen beim Zahlenschloss am Fahrrad)

Wie viele M�glichkeiten hat ein k=4 stelliges Zahlenschloss mit n=6 Ziffern an jeder Stelle?
Das entspricht der Anzahl der M�glichkeiten bei 4 maligem W�rfeln mit einem W�rfel mit 6 unterscheidbaren Fl�chen, wenn die Reihenfolge wichtig ist.
Das entspricht ebenso der Ziehung von 4 Kugeln bei 6 unterscheidbaren Kugeln, wenn die Kugeln jedes Mal zur�ckgelegt werden und die Reihenfolge auch hier wichtig ist.

F�r die Zahl der M�glichkeiten gilt (Die M�glichkeiten sind alle gleichwahrscheinlich.):

Nn,k = nk (Variationen mit Wiederholung)
N6,4 = 64 = 1296

Die Wahrscheinlichkeit, den richtigen Code des Fahrradschlosses zu erraten, betr�gt dann:

Pn,k = 1 / Nn,k
P6,4 = 1 / N6,4 = 1 / 1296 = 0,0007716 = 0,07716%

Genau so gro� ist z.B. die Wahrscheinlichkeit, beim 4 maligen W�rfeln mit einem W�rfel nur Sechsen zu w�rfeln.

Beispiel 5 (4 Richtige bei Lotto 6 aus 49)

Es werden k=6 Kugeln von n=49 unterscheidbaren Kugeln ausgew�hlt, wobei r=6 Kugeln gezogen und nicht zur�ckgelegt werden.
Wie gro� ist die Wahrscheinlichkeit, dass sich unter den k=6 ausgew�hlten Kugeln m=4 "richtige", also gezogene Kugeln befinden? Die Reihenfolge der Auswahl soll keine Rolle spielen.

Herleitung: Die Wahrscheinlichkeit f�r die Auswahl von m=4 �richtigen� Kugeln ist gleich der Anzahl der Kombinationen, 4 von 6 �richtigen� Kugeln auszuw�hlen,
multipliziert mit der Anzahl der Kombinationen, 2 von 43 �falschen� Kugeln auszuw�hlen, geteilt durch die Anzahl der Kombinationen, irgendwelche 6 Kugeln auszuw�hlen.

F�r die Wahrscheinlichkeit gilt also:

P = (rm) · (n�rk�m) / (nk) (hypergeometrische Verteilung)
P = (64) · (432) / (496) = (6!/(2!·4!)) · (43!/(2!·41!)) / (49!/(6!·43!))
= (6 · 5 · 4 · 3 / (1 · 2 · 3 · 4)) · (43 · 42 / (1 · 2)) · (49 · 48 · 47 · 46 · 45 · 44 / (1 · 2 · 3 · 4 · 5 · 6))
= 13.545 / 13.983.816 = 1 / 1032,3969 = 0,00096862 = 0,096862%

Die Formel gilt nat�rlich auch, wenn anders als in diesem Beispiel die Anzahl k der ausgew�hlten Kugeln kleiner ist als die Anzahl r der gezogenen Kugeln (wie z.B. bei KENO).
Beispiel: k=5 ausgew�hlte Kugeln, m=3 "richtige" Kugeln, r=6 gezogene Kugeln, n=49 Kugeln insgesamt
F�r die Wahrscheinlichkeit, unter diesen Bedingungen 3 "richtige" Kugeln auszuw�hlen, gilt:

P = (63) · (432) / (495) = 20 · 903 / 1.906.884 = 1 / 105,5860 = 0,947095%

Ebenso gilt die Formel, wenn die Anzahl k der ausgew�hlten Kugeln gr��er ist als die Anzahl r der gezogenen Kugeln (wie z.B. bei einem Lotto-System).
Beispiel: k=12 ausgew�hlte Kugeln, m=3 "richtige" Kugeln, r=6 gezogene Kugeln, n=49 Kugeln insgesamt
F�r die Wahrscheinlichkeit, unter diesen Bedingungen mindestens einmal 3 "richtige" Kugeln (aber auch nicht mehr "richtige" Kugeln) auszuw�hlen, gilt:

P = (63) · (439) / (4912) = 20 · 563.921.995 / 9.226.373.484 = 1 / 8,180541 = 12,2241%

Wenn die Anzahl k der ausgew�hlten Kugeln gr��er ist als die Anzahl r der gezogenen Kugeln, dann handelt es sich quasi um einen "System-Tipp", der aus vielen "Einzel-Tipps" besteht.
Deshalb muss man die Aussage "3 "richtige" Kugeln" durch den Ausdruck "mindestens einmal 3 "richtige" Kugeln (aber auch nicht mehr "richtige" Kugeln)" ersetzen.

Weitere Berechnungen zu Wahrscheinlichkeiten beim Lotto findet man auf der Lotto-Seite.

Beispiel 6 (Anzahl unterschiedlicher Spiele, Spieltage und Spielrunden bei Fu�ballmannschaften)

Wie viele M�glichkeiten Nn gibt es, f�r n = 18 Fu�ballmannschaften unterschiedliche Spiele aus jeweils 2 Mannschaften zusammenzustellen?

Nn = (n2) = n · (n � 1) / 2
N18 = (182) = 18 · (18 � 1) / 2 = 153

Wie viele M�glichkeiten Nn gibt es, f�r n = 18 Fu�ballmannschaften unterschiedliche Spieltage mit jeweils n/2 = 9 Spielen zusammenzustellen?

Nn = (n2) · (n-22) · (n-42) · ... · (22) / (n/2)!
N12 = (182) · (162) · (142) · ... · (22) / 9! = 153 · 120 · 91 · 66 · 45 · 28 · 15 · 6 · 1 / 362.880 = 34.459.425
oder
Nn = 1 · 3 · 5 · ... · (n�1)
N12 = 1 · 3 · 5 · ... · 17 = 34.459.425

Wie viele M�glichkeiten Nn gibt es, f�r n Fu�ballmannschaften unterschiedliche Spielrunden mit jeweils n�1 Spieltagen zusammenzustellen,
wobei in jeder Spielrunde jede Mannschaft genau einmal gegen jede andere Mannschaft spielt?

N2 = 1! · 1 = 1 · 1 = 1
N4 = 3! · 1 = 6 · 1 = 6
N6 = 5! · 6 = 120 · 6 = 720
N8 = 7! · 6240 = 5040 · 6240 = 31.449.600
N10 = 9! · 1.225.566.720 = 362.880 · 1.225.566.720 = 444.733.651.353.600

Schon durch das Austauschen von Spieltagen in einer Spielrunde ergeben sind unterschiedliche Spielrunden. Bei n�1 Spieltagen pro Spielrunde erh�lt man (n�1)! M�glichkeiten,
die Spieltage in unterschiedlicher Reihenfolge anzuordnen (Permutationen ohne Wiederholung). Dies wird mit dem Fakult�tsausdruck in der Rechnung ber�cksichtigt.

Beispiel 7 (Ziehen von zum Teil gleichen Kugeln ohne Zur�cklegen)

In einer Urne liegen n1=12 rote Kugeln, n2=8 gr�ne Kugeln und n3=4 gelbe Kugeln.
Es werden k=12 Kugeln von diesen n=24 Kugeln ausgew�hlt, wobei die Kugeln nicht zur�ckgelegt werden.
Wie gro� ist die Wahrscheinlichkeit, dass sich unter diesen k=12 Kugeln genau k1=7 rote Kugeln, k2=3 gr�ne Kugeln und k3=2 gelbe Kugeln befinden?

F�r die Wahrscheinlichkeit P gilt dann:

P = (n1k1) · (n2k2) · (n3k3) / (nk) (verallgemeinerte hypergeometrische Verteilung) (n = n1 + n2 + n3) (k = k1 + k2 + k3)
P = (127) · (83) · (42) / (2412) = (12!/(7!·5!)) · (8!/(3!·5!)) · (4!/(2!·2!)) / (24!/(12!·12!))
= 792 · 56 · 6 / 2704156 = 266112 / 2704156 = 0,0984085 = 9,84085%

Beispiel 8 ("Kopf" oder "Zahl" beim M�nzwurf)

Wie gro� ist Wahrscheinlichkeit, mit n=8 W�rfen einer M�nze (k=2 M�glichkeiten: "Kopf" oder "Zahl") genau m=4 mal �Kopf� (r=1 M�glichkeit) zu erzielen? F�r die Wahrscheinlichkeit gilt:

Pn,m = (nm) · pm · (1�p)n�m (Binomialverteilung) (p = r/k)
P8,4 = (84) · (1/2)4 · (1�1/2)8�4 = (84) · (1/2)8 = 70 / 256 = 0,2734375 = 27,34375%

Alle M�glichkeiten:

P8,0 = P8,8 = 1 / 256 = 0,00390625 = 0,390625%
P8,1 = P8,7 = 8 / 256 = 0,03125 = 3,125%
P8,2 = P8,6 = 28 / 256 = 0,109375 = 10,9375%
P8,3 = P8,5 = 56 / 256 = 0,21875 = 21,875%
P8,4 = 70 / 256 = 0,2734375 = 27,34375%

Beispiel 9 (W�rfeln einer bestimmten Anzahl von bestimmten Augenzahlen)

Wie gro� ist die Wahrscheinlichkeit, mit n=12 W�rfen eines W�rfels (k=6) genau m=2 mal eine �Sechs� (r=1) zu erzielen? F�r die Wahrscheinlichkeit gilt:

Pn,m = (nm) · pm · (1�p)n�m (Binomialverteilung) (p = r/k)
P12,2 = (122) · (1/6)2 · (1�1/6)12�2 = (122) · (1/6)2 · (5/6)10 = 0,296094 = 29,6094%

Anmerkung: Das entspricht auch der Wahrscheinlichkeit, die Augenzahl von genau 2 der 12 W�rfe richtig vorherzusagen.

Weitere Beispiele:

P12,0 = 0,112157 = 11,2157%
P12,1 = 0,269176 = 26,9176%
P12,2 = 0,296094 = 29,6094%
P12,3 = 0,197396 = 19,7396%
P12,4 = 0,088828 = 8,8828%
P12,5 = 0,028425 = 2,8425%
P12,6 = 0,006632 = 0,6632%
P12,7 = 0,001137 = 0,1137%
P12,8 = 0,000142 = 0,0142%
P12,9 = 0,000013 = 0,0013%
P12,10 = 0,000001 = 0,0001%

Wie gro� ist die Wahrscheinlichkeit, mit n=12 W�rfen eines W�rfels (k=6) genau m1=2 mal eine �Eins� (r1=1), genau m2=7 mal eine Primzahl (r2=3) und genau m3=3 mal eine zusammengesetzte Zahl (r3=2) zu erzielen? Es gilt:

P = (n! / (m1!·m2!·m3!)) · p1m1 · p2m2 · p3m3 (Multinomialverteilung oder Polynomialverteilung) (p1 = r1/k, p2 = r2/k, p3 = r3/k)
P = (12! / (2!·7!·3!)) · (1/6)2 · (1/2)7 · (1/3)3 = 0,063657 = 6,3657%

Beispiel 10 (W�rfeln einer bestimmten Augenzahl)

Wie gro� ist die Wahrscheinlichkeit, mit n=4 W�rfen eines W�rfels (k=6) mindestens einmal eine �Sechs� zu erzielen?
Die Wahrscheinlichkeit errechnet sich als 1 minus der Wahrscheinlichkeit, mit 4 W�rfen keine �Sechs� zu erzielen:

Pn,k = 1 � (1 � 1/k)n; p = 1/k
P4,6 = 1 � (1 � 1/6)4 = 1 � 625/1296 = 671/1296 = 0,517747 = 51,7747%

F�r n=5 W�rfe gilt: P5,6 = 1 � (1 � 1/6)5 = 1 � 3125/7776 = 4651/7776 = 59,8122%
Und f�r n=6 W�rfe: P6,6 = 1 � (1 � 1/6)6 = 1 � 15625/46656 = 31031/46656 = 66,5102%

F�r einen Dodekaeder-W�rfel (k=12) ist die Wahrscheinlichkeit, mit k=8 W�rfen mindestens einmal eine "Zw�lf" zu erzielen: P8,12 = 1 � (11/12)8 = 50,1470%

Wenn k sehr gro� ist, der "W�rfel" also sehr viele gleichartige Fl�chen hat, gilt gen�hert f�r die Wahrscheinlichkeit:

Pn,k = 1 � (1 � 1/k)n = 1 � ((1 � 1/k)k)n/k = 1 � (1/e)n/k = 1 � e� n/k

Wenn man dann genau so viele W�rfe macht wie der "W�rfel" Fl�chen hat (n=k), ist die Wahrscheinlichkeit, mindestens einmal die gr��te Augenzahl n zu erzielen, also gleich 1 � 1/e = 63,2121%.

Nach n/k aufgel�st ergibt sich: n/k = � ln(1 � Pn,k)

Eine Wahrscheinlichkeit Pn,k von 50% wird erreicht, wenn das Verh�ltnis n/k = � ln(1 � 50%) = � ln(1 � 1/2) = ln(2) = 0,693147 betr�gt.
Und eine Wahrscheinlichkeit Pn,k von 95%, wenn das Verh�ltnis n/k = � ln(1 � 95%) = � ln(1 � 0,95) = � ln(1/20) = ln(20) = 2,995732 betr�gt.

Au�erdem ist nat�rlich richtig, dass man mit einem "normalen" W�rfel im Mittel 6 W�rfe braucht, um eine 6 zu w�rfeln.

Wenn man z.B. mit 4 W�rfen mit einer Wahrscheinlichkeit von 51,7747% mindestens eine 6 w�rfelt, w�rfelt man also mit einer Wahrscheinlichkeit
von (5/6)4 = 625/1296 = 48,2253% keine 6. Diese Wahrscheinlichkeiten gelten nat�rlich f�r jede der 6 Augenzahlen.
Das bedeutet aber auch, dass bei 4 W�rfen im Mittel 48,2253% · 6 = 2,8935 Augenzahlen nicht gew�rfelt werden.

Bei n=4 W�rfen und k=6 unterschiedlichen Augenzahlen betr�gt also die mittlere Anzahl Z der erzielten unterschiedlichen Augenzahlen:

Zn,k = Z4,6 = k · (1 � ((k�1)/k)n) = 6 · (1 � (5/6)4) = 6 · (1 � 0,482253) = 6 · 0,517747 = 3,1065

Beispiel 11 (W�rfeln von bestimmten Augenzahlen mit zwei W�rfeln)

Wie gro� ist die Wahrscheinlichkeit, mit n=24 W�rfen mit m=2 W�rfeln (k=6) mindestens einmal m=2 "Sechsen" zu erzielen?

Herleitung:
Die Wahrscheinlichkeit, mit einem Wurf von m=2 W�rfeln (k=6) m=2 "Sechsen" zu erzielen, betr�gt (1/k)m.
Die Wahrscheinlichkeit, mit einem Wurf von m=2 W�rfeln (k=6) keine m=2 "Sechsen" zu erzielen, betr�gt 1 � (1/k)m.
Die Wahrscheinlichkeit, mit n=24 W�rfen mit m=2 W�rfeln (k=6) keinmal m=2 "Sechsen" zu erzielen, betr�gt (1 � (1/k)m)n.
Die Wahrscheinlichkeit, mit n=24 W�rfen mit m=2 W�rfeln (k=6) mindestens einmal m=2 "Sechsen" zu erzielen, ist dann:

Pn,k,m = 1 � (1 � (1/k)m)n
P24,6,2 = 1 � (1 � (1/6)2)24 = 1 � (35/36)24 = 1 � 0,508596 = 0,491404 = 49,1404%

Beispiel 12 (Geburtstag am gleichen Tag von mindestens 2 Kindern)

Wie gro� ist die Wahrscheinlichkeit, dass von k=23 Kindern mindestens zwei am gleichen Tag Geburtstag haben? Das entspricht der Wahrscheinlichkeit, mindestens eine Kugel zweimal zu ziehen, wenn man von n=365 unterscheidbaren Kugeln 23 Kugeln zieht und die gezogene Kugel jeweils wieder zur�cklegt (siehe auch die Geburtstagsr�tsel-Seite).

Die Wahrscheinlichkeit errechnet sich als 1 minus der Anzahl der M�glichkeiten, bei denen keine Kugel mehrmals gezogen wurde (Variationen ohne Wiederholung), geteilt durch die Anzahl aller M�glichkeiten (Variationen mit Wiederholung). Die Reihenfolge der Ziehung ist wichtig, damit alle M�glichkeiten die gleiche Wahrscheinlichkeit haben. Es gilt also:

Pn,k = 1 � (n!/(n�k)!) / nk
P365,23 = 1 � (365! / 342!) / 36523 = 1 � 365 · 364 ·...· 343 / 36523 = 1 � 0,492703 = 0,507297 = 50,7297%

Bei 2 Kindern ist die Wahrscheinlichkeit, dass alle an verschiedenen Tagen Geburtstag haben, gleich (364/365).
Bei 3 Kindern ist die Wahrscheinlichkeit, dass alle an verschiedenen Tagen Geburtstag haben, gleich (364/365) · (363/365).
Bei k Kindern ist die Wahrscheinlichkeit, dass alle an verschiedenen Tagen Geburtstag haben, gleich n · (n�1) · (n�2) ·...· (n�k+1) / nk = (n!/(n�k)!) / nk.

Beispiel 13 (Geburtstag am gleichen Tag von einer bestimmten Anzahl von Kindern)

Wie gro� ist die Wahrscheinlichkeit, mit k=23 W�rfen eines �W�rfels� mit 365 gleichen Fl�chen (n=365) nur Einlinge (g=0), einen Zwilling (g=1, z=2), einen Drilling (g=1, z=3), einen Vierling (g=1, z=4), einen F�nfling (g=1, z=5), zwei Zwillinge (g=2, z=2), drei Zwillinge (g=3, z=2), vier Zwillinge (g=4, z=2), f�nf Zwillinge (g=5, z=2), einen Zwilling und einen Drilling (g=2, z=2 bzw. z=3), zwei Zwillinge und einen Drilling (g=3, z=2 bzw. z=3) oder drei Zwillinge und einen Drilling (g=4, z=2 bzw. z=3) zu erzielen?

Das entspricht der Wahrscheinlichkeit, dass von 23 Kindern keines, genau 2, 3, 4, 5, 2 mal 2, 3 mal 2, 4 mal 2, 5 mal 2, 2 und 3, 2 mal 2 und 3 oder 3 mal 2 und 3 am gleichen Tag Geburtstag haben. Die Wahrscheinlichkeiten betragen:

P = (k! / z!g) · (n�gk�g·z) · (ng) / nk

Dabei ist:
k: Anzahl der W�rfe
n: Anzahl der Seiten des "W�rfels"
g: Anzahl der Mehrlinge
z: Anzahl der "W�rfel" f�r einen Mehrling
Weitere Erl�uterungen: siehe Beispiel 14

Nur Einlinge:
P = (23! / z!0) · (365�023�0) · (3650) / 36523 = 0,492703 = 49,2703%

Genau ein Zwilling:
P = (23! / 2!1) · (365�123�2) · (3651) / 36523 = 0,363422 = 36,3422%

Genau ein Drilling:
P = (23! / 3!1) · (365�123�3) · (3651) / 36523 = 0,007395 = 0,7395%

Genau ein Vierling:
P = (23! / 4!1) · (365�123�4) · (3651) / 36523 = 0,000107 = 0,0107%

Genau ein F�nfling:
P = (23! / 5!1) · (365�123�5) · (3651) / 36523 = 0,000001 = 0,0001%

Genau zwei Zwillinge:
P = (23! / 2!2) · (365�223�4) · (3652) / 36523 = 0,110928 = 11,0928%

Genau drei Zwillinge:
P = (23! / 2!3) · (365�323�6) · (3653) / 36523 = 0,018327 = 1,8327%

Genau vier Zwillinge:
P = (23! / 2!4) · (365�423�8) · (3654) / 36523 = 0,001801 = 0,1801%

Genau f�nf Zwillinge:
P = (23! / 2!5) · (365�523�10)· (3655) / 36523 = 0,000109 = 0,0109%

Genau ein Zwilling und ein Drilling (Die obige Formel ist hier entsprechend erweitert worden.):
P = (2! / (1! · 1!)) · (23! / (2! · 3!)) · (365�223�(2+3)) · (3652) / 36523 = 0,004073 = 0,4073%

Genau zwei Zwillinge und ein Drilling (Die obige Formel ist hier entsprechend erweitert worden.):
P = (3! / (2! · 1!)) · (23! / (2!2 · 3!)) · (365�323�(2+2+3)) · (3653) / 36523 = 0,000900 = 0,0900%

Genau drei Zwillinge und ein Drilling (Die obige Formel ist hier entsprechend erweitert worden.):
P = (4! / (3! · 1!)) · (23! / (2!3 · 3!)) · (365�423�(2+2+2+3)) · (3654) / 36523 = 0,000104 = 0,0104%

Beispiel 14 (Wahrscheinlichkeit f�r Kniffel, Viererpasch, Dreierpasch und Full House)

Wie gro� ist die Wahrscheinlichkeit, mit k=5 W�rfen eines W�rfels (n=6) nur Einlinge (g=0), einen Zwilling (g=1, z=2), einen Drilling (g=1, z=3), einen Vierling (g=1, z=4), einen Kniffel (g=1, z=5), zwei Zwillinge (g=2, z=2) oder einen Zwilling und einen Drilling (g=2, z=2 bzw. z=3) zu erzielen? Die Wahrscheinlichkeiten betragen:

P = (k! / z!g) · (n�gk�g·z) · (ng) / nk (Formel gilt nur f�r Mehrlinge mit gleicher Anzahl von W�rfeln!)

Dabei ist:
k: Anzahl der W�rfe
n: Anzahl der Seiten des W�rfels (Anzahl der Augenzahlen)
g: Anzahl der Mehrlinge
z: Anzahl der W�rfel f�r einen Mehrling
(nk): Gesamtanzahl der W�rfelm�glichkeiten (Variationen mit Wiederholung)
(ng): Anzahl der M�glichkeiten, g verschiedene Mehrlinge bei n Augenzahlen zu kombinieren (Kombinationen ohne Wiederholung)
k�g�z: Anzahl der Einlinge
n�g: Anzahl der Augenzahlen, die f�r diese Einlinge noch zur Verf�gung stehen
(n�gk�g�z): Anzahl der M�glichkeiten, k�g�z verschiedene Einlingen bei n�g Augenzahlen zu kombinieren (Kombinationen ohne Wiederholung)
(k! / z!g): Anzahl der verschiedenen Reihenfolgen der (gleichartigen) Mehrlinge mit den Einlingen (Permutationen mit Wiederholung)

Nur Einlinge (alle Augenzahlen verschieden):
P = (5! / z!0) · (6�05�0) · (60) / 65 = 720/7776 = 0,092593 = 9,2593%

Genau ein Zwilling (genau zwei gleiche Augenzahlen):
P = (5! / 2!1) · (6�15�2) · (61) / 65 = 3600/7776 = 0,462963 = 46,2963%

Genau ein Drilling (genau drei gleiche Augenzahlen: entspricht Dreierpasch ohne Full House, Vierling und Kniffel):
P = (5! / 3!1) · (6�15�3) · (61) / 65 = 1200/7776 = 0,154321 = 15,4321%

Genau ein Vierling (genau vier gleiche Augenzahlen: entspricht Viererpasch ohne Kniffel):
P = (5! / 4!1) · (6�15�4) · (61) / 65 = 150/7776 = 0,019290 = 1,9290%

Einen Kniffel (f�nf gleiche Augenzahlen):
P = (5! / 5!1) · (6�15�5) · (61) / 65 = 6/7776 = 0,000772 = 0,0772%

Genau zwei Zwillinge (zwei gleiche Augenzahlen und zus�tzlich zwei andere gleiche Augenzahlen)
P = (5! / 2!2) · (6�25�4) · (62) / 65 = 1800/7776 = 0,231481 = 23,1481%

Ein Drilling und ein Zwilling (drei gleiche Augenzahlen und zus�tzlich zwei andere gleiche Augenzahlen: Full House) (Die obige Formel ist hier entsprechend erweitert worden.):
P = (2! / (1! · 1!)) · (5! / (3! · 2!)) · (6�25�(3+2)) · (62) / 65 = 300/7776 = 0,038580 = 3,8580% (Z�hlt man einen Kniffel auch als Full House, erh�lt man P = 306/7776.)

Wichtig: Da Drilling und Zwilling verschiedene Mehrlinge sind, entsteht auch bei zwei gleichen Augenzahlen eine weitere Permutation: (2! / (1! · 1!)).
Es gibt hier also 2 Mehrlinge, wobei jeder Mehrling (Drilling bzw. Zwilling) jeweils nur 1-mal vorkommt.

Die entsprechenden Wahrscheinlichkeiten beim Kniffel mit 3 W�rfen findet man auf der Kniffel-Seite.

Beispiel 15 (Wahrscheinlichkeit f�r gro�e und kleine Stra�e beim Kniffel)

Wie gro� ist die Wahrscheinlichkeit, mit k=5 W�rfen eines W�rfels mit n=6 (durch die Augenzahlen von 1 bis n) unterscheidbaren Fl�chen genau k bzw. k�1 Augenzahlen zu bekommen, die eine Folge bilden?

Die Wahrscheinlichkeit f�r eine Folge von k=5 Augenzahlen (gro�e Stra�e beim Kniffel) betr�gt (f�r k kle�ner als n+1):

Pn,k = (n � k + 1) · k! / nk
P6,5 = (6 � 5 + 1) · 5! / 65 = 240 / 7776 = 0,030864 = 3,0864%

Die Wahrscheinlichkeit f�r eine Folge von k�1=4 Augenzahlen ("reine" kleine Stra�e beim Kniffel) betr�gt (f�r k kle�ner als n+2 und gr��er als 2):

Qn,k = (2 · ((k � 1)/2! + (n � k)) + (n � k) · ((k � 1)/2! + (n � k � 1)))· k! / nk
Q6,5 = (2 · (4/2 + 1) + 1 · (4/2 + 0))· 5! / 65 = 960 / 7776 = 0,123457 = 12,3457%

Herleitung: Man unterscheidet zwischen den kleinen Stra�en am Rand (1234 und 3456 bei k=5 W�rfen) und den kleinen Stra�en, die nicht am "Rand" liegen (nur 2345 bei 5 W�rfen).
nk = 65 = 7776 ist die Gesamtzahl der M�glichkeiten (Variationen mit Wiederholung) und k! = 5! = 120 die Anzahl der Permutationen.
Die beiden kleinen Stra�en am "Rande" werden (bei 5 W�rfen) durch den Ausdruck 2 � ((k � 1)/2! + (n � k)) = 2 � ((5 � 1)/2 + (6 � 5)) = 6 beschrieben.
Die erste 2 beschreibt die Anzahl der beiden kleinen "Rand"-Stra�en.
k � 1 = 4 ist die Anzahl der M�glichkeiten, dass die f�nfte Augenzahl mit einer der 4 Augenzahlen der kleinen "Rand"-Stra�e identisch ist.
Deshalb muss hier auch das (ausgeklammerte) k! durch 2! geteilt werden, um die Anzahl der Permutationen richtig zu berechnen, weil eine Augenzahl hier ja immer doppelt vorkommt.
n � k = 1 beschreibt die einzige M�glichkeit, dass die f�nfte Augenzahl nicht mit einer der 4 Augenzahlen der kleinen Stra�e identisch ist (also z.B. 12346 bei der kleinen Stra�e 1234).
Die kleinen Stra�en, die nicht am "Rand" liegt, werden durch den Ausdruck (n � k) � ((k � 1)/2! + (n � k � 1)) = (6 � 5) � ((5 � 1)/2 + (6 � 5 � 1)) = 2 beschrieben.
n � k = 1 beschreibt bei k=5 W�rfen die Anzahl der kleinen Stra�en, die nicht am "Rand" liegen.
k � 1 = 4 ist die Anzahl der M�glichkeiten, dass die f�nfte Augenzahl mit einer der 4 Augenzahlen der kleinen Stra�e, die nicht am Rand liegt, identisch ist.
Deshalb muss hier auch wieder durch 2! geteilt werden, um die Anzahl der Permutationen richtig zu berechnen.
n � k � 1 = 0 beschreibt die Anzahl der M�glichkeiten, dass die f�nfte Augenzahl nicht mit einer der 4 Augenzahlen der kleinen Stra�e identisch ist.
Diese Anzahl ist bei der kleinen Stra�e 2345 nat�rlich gleich Null. Wenn n nicht gleich 6 und k nicht gleich 5 ist, kann diese Anzahl aber durchaus von Null verschieden sein.
Bei k = 3 W�rfen gibt es z.B. 3 kleine Stra�en, die nicht am Rand liegen, n�mlich 23, 34 und 45. Und f�r jede dieser 3 kleinen Stra�en gibt es n � k � 1 = 2 M�glichkeiten,
dass die dritte Augenzahl nicht mit einer der 2 Augenzahlen der kleinen Stra�en identisch ist (z.B. bei der kleinen Stra�e 23 sind das die 2 M�glichkeiten 235 und 236).
Der Term n � k � 1 f�llt also bei 5 W�rfen mit 6 Augenzahlen weg und die Formel wird dadurch einfacher.
Allgemein gesagt, f�llt der Term immer weg, wenn die Anzahl der W�rfe um 1 kleiner ist als die Anzahl der Fl�chen (Augenzahlen) auf dem "W�rfel".

Die Wahrscheinlichkeit f�r eine Folge von k�2=3 Augenzahlen ("reine" noch kleinere Stra�e) betr�gt �brigens: 2280/7776 = 29,3210%

Die Wahrscheinlichkeit f�r eine Folge von k=5 oder k�1=4 Augenzahlen (kleine Stra�e beim Kniffel) betr�gt:

R6,5 = P6,5 + Q6,5 = 1200 / 7776 = 0,154321 = 15,4321%

Die entsprechenden Wahrscheinlichkeiten beim Kniffel mit 3 W�rfen findet man auf der Kniffel-Seite.

Beispiel 16 (Anzahl unterschiedlicher Lottozahlen nach einer Reihe von Ziehungen)

Wie viele verschiedene Lottozahlen sind durchschnittlich nach n Ziehungen gezogen worden?

Nach einer Ziehung sind 6/49 � 49 = 6 verschiedene Lottozahlen gezogen worden. Es bleiben 49 � 6 = 43 noch nicht gezogene Lottozahlen.

Nach 2 Ziehungen sind im Mittel 6 + 6/49 � 43 = 11,2653 verschiedene Lottozahlen gezogen worden. Es bleiben 49 � 11,2653 = 37,7347 nicht gezogene Lottozahlen. Wegen der
6 gezogenen Lottozahlen muss man immer die Anzahl der noch nicht gezogenen Lottozahlen mit 6/49 multiplizieren, um die zus�tzliche Anzahl der gezogenen Lottozahlen zu ermitteln.

Nach 3 Ziehungen sind im Mittel 11,2653 + 6/49 � 37,7347 = 15,8859 verschiedene Lottozahlen gezogen worden. Es bleiben 49 � 15,8859 = 33,1141 noch nicht gezogene Lottozahlen.

Die mittlere Anzahl unterschiedlicher Lottozahlen nach n Ziehungen:

n = 01: 06,0000
n = 02: 11,2653
n = 03: 15,8859
n = 04: 19,9407
n = 05: 23,4990
n = 06: 26,6215
n = 07: 29,3618
n = 08: 31,7664
n = 09: 33,8767
n = 10: 35,7285
n = 11: 37,3536
n = 12: 38,7797
n = 13: 40,0311
n = 14: 41,1294
n = 15: 42,0931
n = 16: 42,9389
n = 17: 43,6810
n = 18: 44,3323
n = 19: 44,9039
n = 20: 45,4055
n = 21: 45,8456
n = 22: 46,2319
n = 23: 46,5708
n = 24: 46,8683
n = 25: 47,1293
n = 26: 47,3584
n = 27: 47,5594
n = 28: 47,7358
n = 29: 47,8906
n = 30: 48,0264
n = 31: 48,1456
n = 32: 48,2503
n = 33: 48,3421
n = 34: 48,4226
n = 35: 48,4933
n = 36: 48,5554
n = 37: 48,6098
n = 38: 48,6576
n = 39: 48,6995
n = 40: 48,7363
n = 41: 48,7686
n = 42: 48,7969
n = 43: 48,8218
n = 44: 48,8436
n = 45: 48,8628
n = 46: 48,8796
n = 47: 48,8943
n = 48: 48,9074
n = 49: 48,9186
n = 50: 48,9286
n = 51: 48,9373
n = 52: 48,9450

Beispiel 17 (Radioaktiver Zerfall)

Wie gro� ist die Wahrscheinlichkeit, dass w�hrend der Messzeit bei zu Beginn n unzerfallenen Atomen genau m Treffer (zerfallene Atome) erzielt werden, wobei ein bestimmtes Atom w�hrend der Messzeit mit der Wahrscheinlichkeit p zerf�llt? Das entspricht der Wahrscheinlichkeit, mit n W�rfen m Treffer zu erzielen, wobei die Wahrscheinlichkeit pro Wurf f�r einen Treffer p = m/n betr�gt. F�r die Wahrscheinlichkeit gilt:

Pn,m,p = ((n·p)m / m!) · e�n·p (Poisson-Verteilung)

Damit die Formel gilt, muss p sehr klein sein. Hat man nun so viele unzerfallene Atome n, dass n·p = 1 ist, dass also w�hrend der Messzeit im Mittel ein Atom zerf�llt, l�sst sich die Wahrscheinlichkeit berechnen, dass w�hrend der Messzeit kein, genau ein, genau zwei usw. Atome zerfallen:

Pm = (1 / m!) · e�1 = 1 / (m! · e)

P0 = 0,367879 = 36,7879%
P1 = 0,367879 = 36,7879%
P2 = 0,183940 = 18,3940%
P3 = 0,061313 = 6,1313%
P4 = 0,015328 = 1,5328%
P5 = 0,003066 = 0,3066%
P6 = 0,000511 = 0,0511%
P7 = 0,000073 = 0,0073%

Die gleiche Rechnung ergibt sich, wenn man wissen will, mit welcher Wahrscheinlichkeit man pro Tag keinen, genau einen, genau zwei Briefe usw. bekommt,
wenn im Mittel pro Tag ein Brief eintrifft und die Briefe keine Beziehung zueinander haben. Die Wahrscheinlichkeit, genau einen Brief zu bekommen,
ist also genau so gro� wie die Wahrscheinlichkeit, keinen zu bekommen. Sie betr�gt 36,7879%.

Die Anzahl unzerfallener Atome N nach der Zeit t betr�gt �brigens:

N = n · e�t/τ

Dabei ist n die Anzahl der unzerfallenen Atome zur Zeit t=0 und τ die mittlere Lebensdauer eines Atoms.
Nach der Zeit t = τ betr�gt die Anzahl der unzerfallenen Atome also nur noch:

N = n · e�1 = (1/e) · n = 0,367879 · n

Die Halbwertseit t1/2, nach der sich die Anzahl N der unzerfallenen Atome halbiert hat, erh�lt man,
wenn man in die Formel f�r N den Wert n/2 und f�r t den Wert t1/2 einsetzt und nach t1/2 aufl�st:

t1/2 = ln(2) · τ = 0,693147 · τ

F�r τ gilt dann: τ = t1/2 / ln(2) = 1,442695 · t1/2

Beispiel 18 (Briefe und zugeh�rige Briefumschl�ge)

Wie viele M�glichkeiten gibt es, n=7 Briefe so in n=7 Briefumschl�ge zu stecken, dass sich in keinem Umschlag der zugeh�rige Brief befindet?
Die Anzahl der M�glichkeiten (fixpunktfreien Permutationen) Nn betr�gt:

Nn = !n = (n!/0! � n!/1! + n!/2! � n!/3! + ... n!/n!) = n! · (1/0! � 1/1! + 1/2! � 1/3! + ... 1/n!) (!n = Subfakult�t von n)
N7 = !7 = 1854

Die Gesamtzahl der M�glichkeiten, n=7 Briefe in n=7 Briefumschl�ge zu stecken, betr�gt n! = 7! = 5040. (Permutationen ohne Wiederholung)

Die Wahrscheinlichkeit Pn, dass sich bei n Briefumschl�gen per Zufall in keinem Umschlag der zugeh�rige Brief befindet, betr�gt also:

Pn = Nn / n! = !n / n!

P1 = !1 / 1! = 0/1 = 0,000%
P2 = !2 / 2! = 1/2 = 50,000%
P3 = !3 / 3! = 2/6 = 33,333%
P4 = !4 / 4! = 9/24 = 37,500%
P5 = !5 / 5! = 44/120 = 36,667%
P6 = !6 / 6! = 265/720 = 36,806%
P7 = !7 / 7! = 1854/5040 = 36,786%
P8 = !7 / 8! = 14.833/40320 = 36,788%
P9 = !9 / 9! = 133.496/362.880 = 36,788%

Schon f�r kleine n gilt in guter N�herung: !n = n! · 1/e.

Deshalb geht Pn f�r gro�e n gegen: Pn = 1/e · n! / n! = 1/e = 36,787944%

Die Anzahl der M�glichkeiten, n=7 Briefe so in n=7 Briefumschl�ge zu stecken, dass sich in k Umschl�gen der zugeh�rige Brief befindet, betr�gt:

Nn,k = (nk) · !(n � k)

N7,0 = (70) · !7 = 1 · 1854 = 1854
N7,1 = (71) · !6 = 7 · 265 = 1855
N7,2 = (72) · !5 = 21 · 44 = 924
N7,3 = (73) · !4 = 35 · 9 = 315
N7,4 = (74) · !3 = 35 · 2 = 70
N7,5 = (75) · !2 = 21 · 1 = 21
N7,6 = (76) · !1 = 7 · 0 = 0
N7,7 = (77) · !0 = 1 · 1 = 1

Beispiel 19 (Socken und Ampeln)

Von n=10 Paar Socken (m=2), die alle verschieden sind, gehen k=6 Socken verloren.
Das entspricht der Ziehung von k=6 Kugeln bei n=10 Paar paarweise gleicher Kugeln.
Wie gro� ist die Wahrscheinlichkeit, dass alle k=6 Socken verschieden sind, also von verschiedenen Paaren stammen? F�r die Wahrscheinlichkeit gilt:

Pn,k = (m1)k · (nk) / (m·nk)
P10,6 = (21)6 · (106) / (206) = 26 · 210 / 38.760 = 20/20 · 18/19 · 16/18 · 14/17 · 12/16 · 10/15 = 112 / 323 = 0,34675 = 34,675%

Die Wahrscheinlichkeit, dass alle k=6 Socken zu k/2=3 Paaren geh�ren, dass also noch 7 vollst�ndige Sockenpaare �brig sind, betr�gt:

Pn,k = (m2)k/2 · (nk/2) / (m·nk)
P10,6 = (22)3 · (103) / (206) = 120 / 38.760 = 15 · (20/20 · 1/19 · 18/18 · 1/17 · 16/16 · 1/15) = 1 / 323 = 0,00310 = 0,310%

Die Wahrscheinlichkeit, dass alle verlorenen 6 einzelnen Socken von verschiedenen Paaren stammen, so dass nur noch 4 vollst�ndige Paare �brig sind, ist also mehr als 100mal so gro� wie die Wahrscheinlichkeit, dass nach dem Verlieren der 6 einzelnen Socken noch 7 vollst�ndige Paare �brig bleiben.

Wie gro� ist nun die Wahrscheinlichkeit, wenn sich unter den verloren gegangenen Socken weder keine Paare noch nur Paare befinden, sondern a = 1 Paar oder a = 2 Paare? Daf�r gilt die erweiterte Formel:

Pn,k,a = (m1)k-2a · (n-ak-2a) · (m2)a · (na) / (m·nk)
P10,6,1 = (21)4 · (94) · (22)1 · (101) / (206) = 20.160 / 38.760 = 52,012%
P10,6,2 = (21)2 · (82) · (22)2 · (102) / (206) = 5040 / 38.760 = 13,003%

Von n=10 Ampeln mit je 3 Lampen (m=3) gehen k=8 Lampen kaputt. Das entspricht der Ziehung von k=8 Kugeln bei n=10 Kugeldrillingen, wobei die Drillinge untereinander jeweils gleich sind. Wie gro� ist die Wahrscheinlichkeit, dass 3 Ampeln jeweils eine kaputte Lampe (a=3), eine Ampel 2 kaputte Lampen (b=1) und eine Ampel 3 kaputte Lampen (c=1) aufweisen? F�r die Wahrscheinlichkeit gilt:

Pn,k,a,b,c = (m1)a · (n-b-ca) · (m2)b · (n-bb) · (m3)c · (nc) / (m·nk)
P10,8,3,1,1 = (31)3 · (83) · (32)1 · (91) · (33)1 · (101) / (308) = 27 · 56 · 3 · 9 · 1 · 10 / (308) = 408.240 / 5.852.925 = 6,975%

Die Anzahl der Kombinationen in allen diesen Beispielen erh�lt man, wenn man die jeweiligen Z�hler nimmt und die Ausdr�cke mit den Potenzen wegl�sst. Die jeweiligen Kombinationen sind aber nicht gleich wahrscheinlich!

Beispiel 20 ("�berraschungen" und �berraschungseier)

Wie gro� ist die Wahrscheinlichkeit, dass bei k=20 Ziehungen (mit Zur�cklegen) von n=8 verschiedenen Kugeln (k >= n) jede Kugel mindestens einmal gezogen wird, wenn die jeweils gezogenen Kugeln wieder zur�ckgelegt werden?

Das entspricht der Wahrscheinlichkeit, beim Kauf von k=20 �berraschungseiern bei insgesamt n=8 verschiedenen gleich h�ufigen "�berraschungen" mindestens von jeder eine bekommen zu haben. F�r die Wahrscheinlichkeit gilt:

Pn,k = Σi=0n (-1)i · (ni) · (1 - i/n)k
P8,20 = 0,53056 = 53,056%

Das ist auch die kleinste Zahl von �berraschungseiern, die man kaufen muss, damit diese Wahrscheinlichkeit �ber 50% liegt.

Man muss �brigens mit einem W�rfel (n=6) mindestens 13-mal w�rfeln, um mit mehr als 50% Wahrscheinlichkeit jede Augenzahl mindestens einmal gew�rfelt zu haben. Hier gilt:

P6,13 = 0,51386 = 51,386%

100% � 51,386% = 48,614% ist dann die Wahrscheinlichkeit, dass bei 13-maligem W�rfeln mindestens eine Augenzahl nicht gew�rfelt wird.

Wie gro� ist die mittlere Zahl von Ziehungen (mit Zur�cklegen), bei der von n verschiedenen Kugeln jede Kugel mindestens einmal gezogen wurde?
Das entspricht der mittleren Zahl von �berraschungseiern, bei der von n verschiedenen "�berraschungen" jede "�berraschung" mindestens einmal vorgekommen ist.
F�r diese mittlere Zahl von Ziehungen gilt:

Zn = Σk=n∞ k · (Pn,k � Pn,k�1) = n · Σi=1n (1/i)

Einige Beispiele:

Z2 = 3 + 0/1 = 3,000000
Z3 = 5 + 1/2 = 5,500000
Z4 = 8 + 1/3 = 8,333333
Z5 = 11 + 5/12 = 11,416667
Z6 = 14 + 7/10 = 14,700000 (= mittlere Zahl von W�rfen, bei der jede Augenzahl mindestens einmal gew�rfelt wurde)
Z7 = 18 + 3/20 = 18,150000
Z8 = 21 + 26/35 = 21,742857
Z9 = 25 + 129/280 = 25,460714
Z10 = 29 + 73/252 = 29,289683
Z11 = 33 + 551/2520 = 33,218651
Z12 = 37 + 551/2310 = 37,238528

Bei k=20 Ziehungen und n=8 verschiedenen �berraschungen betr�gt �brigens die mittlere Anzahl A der erzielten unterschiedlichen �berraschungen:

An,k = A8,20 = n · (1 � ((n�1)/n)k) = 8 · (1 � (7/8)20) = 8 · (1 � 0,069209) = 8 · 0,930791 = 7,4463

Wenn man die Wahrscheinlichkeit wissen will, dass bei k=20 Ziehungen (mit Zur�cklegen) von n=8 verschiedenen Kugeln (k >= n) nicht jede Kugel mindestens einmal gezogen wird, sondern z.B. nur genau m=6 Kugeln, dann gilt daf�r die Wahrscheinlichkeit:

Pn,k,m = (nm) · Σi=0m (-1)m-i · (mi) · (i/n)k
P8,20,6 = 0,07530 = 7,530%

F�r m=n vereinfacht sich die Formel zu:

Pn,k = Σi=0n (-1)n-i · (ni) · (i/n)k

Dies entspricht der obigen Formel, weil die Summanden (-1)i und (1 - i/n)k nur in umgekehrter Reihenfolge addiert werden und sich die Summanden (ni) auch bei Vertauschung der Reihenfolge nicht �ndern.

Beispiel 21 (Aufeinanderfolgende Zahlen bei Lotto 6 aus 49)

Wie gro� ist die Wahrscheinlichkeit, dass beim Lotto 6 aus 49 mindestens zwei aufeinanderfolgende Zahlen gezogen werden?

Die Wahrscheinlichkeit, dass keine aufeinanderfolgenden Zahlen gezogen werden, ist gleich der Anzahl der M�glichkeiten (Kombinationen ohne Wiederholung), in die L�cken zwischen den 43 nicht gezogenen Zahlen (insgesamt gibt es 44 L�cken einschlie�lich Anfang und Ende) jeweils h�chstens eine gezogene Zahl zu platzieren, geteilt durch die Anzahl der M�glichkeiten f�r 6 Richtige. F�r die Wahrscheinlichkeit, dass mindestens zwei aufeinanderfolgende Zahlen gezogen werden, gilt dann:

P = 1 � (446) / (496) = 1 � (44! / (6!·38!)) / (49! / (6!·43!)) = 1 � 7.059.052 / 13.983.816 = 1 � 22.919 / 45.402

P = 1 � 0,504802 = 0,495198 = 49,5198%

Mit einer Wahrscheinlichkeit von 49,5198% gibt es also bei einer Ziehung mindestens zwei aufeinanderfolgende Lottozahlen.

F�r eine bestimmte Anzahl aufeinanderfolgender Lottozahlen muss man f�r die 44 L�cken die Permutationen mit Wiederholung bestimmen.
Es gelten die folgenden Wahrscheinlichkeiten P:

6 aufeinanderfolgende Lottozahlen: P = (44! / (43!·1!)) / (49 6) = 44 / 13.983.816 = 1 : 317.814 = 0,0003%
5 aufeinanderfolgende Lottozahlen: P = (44! / (42!·1!·1!)) / (49 6) = 1892 / 13.983.816 = 1 : 7391,02 = 0,0135%
4 und 2 aufeinanderfolgende Lottozahlen: P = (44! / (42!·1!·1!)) / (49 6) = 1892 / 13.983.816 = 1 : 7391,02 = 0,0135%
Genau 4 aufeinanderfolgende Lottozahlen: P = (44! / (41!·2!·1!)) / (49 6) = 39.732 / 13.983.816 = 1 : 351,9535 = 0,2841%
Zweimal 3 aufeinanderfolgende Lottozahlen: P = (44! / (42!·2!)) / (49 6) = 946 / 13.983.816 = 1 : 14.782,04 = 0,0068%
3 und 2 aufeinanderfolgende Lottozahlen: P = (44! / (41!·1!·1!·1!)) / (49 6) = 79.464 / 13.983.816 = 1 : 175,9767 = 0,5683%
Genau 3 aufeinanderfolgende Lottozahlen: P = (44! / (40!·3!·1!)) / (49 6) = 543.004 / 13.983.816 = 1 : 25,7527 = 3,8831%
Dreimal 2 aufeinanderfolgende Lottozahlen: P = (44! / (41!·3!)) / (49 6) = 13.244 / 1.3983.816 = 1 : 1055,86 = 0,0947%
Zweimal 2 aufeinanderfolgende Lottozahlen: P = (44! / (40!·2!·2!)) / (49 6) = 814.506 / 13.983.816 = 1 : 17,1685 = 5,8246%
Genau 2 aufeinanderfolgende Lottozahlen: P = (44! / (39!·4!·1!)) / (49 6) = 5.430.040 / 13.983.816 = 1 : 2,5753 = 38,8309%
Keine aufeinanderfolgenden Lottozahlen: P = (44! / (38!·6!)) / (49 6) = 7.059.052 / 13.983.816 = 1 : 1,9810 = 50,4802%

Herleitung: Bei einer Lottoziehung gibt es 6 gezogene und 43 nicht gezogene Zahlen.

1. Beispiel: Keine aufeinanderfolgenden Lottozahlen
Hier darf sich zwischen zwei nicht gezogenen Lottozahlen h�chstens eine gezogene Lottozahl befinden. Ebenso vor der ersten und nach der letzten nicht gezogenen Lottozahl.
Bei 43 nicht gezogenen Lottozahlen gibt es 44 solcher L�cken (eine am Anfang, 42 dazwischen und eine am Ende).
Wenn man eine L�cke ohne gezogene Lottozahl mit "0", eine mit einer Lottozahl mit "1" und eine mit zwei Lottozahlen mit "2" bezeichnet, entsteht immer eine Zifferfolge mit 44 Ziffern.
00000010000110000000000000010000000100000001 zum Beispiel entspricht immer eineindeutig den Lottozahlen 7, 13, 15, 31, 40, 49.
Wenn es keine aufeinanderfolgen Lottozahlen gibt, enth�lt die Ziffernfolge immer genau 38 Nullen und 6 Einsen.
Wenn man von dieser Ziffernfolge alle Permutationen mit Wiederholung berechnet, erh�lt man also alle Lottozahlenkombinationen ohne aufeinanderfolgende Lottozahlen.
Anzahl der Permutationen mit Wiederholung: 44! / (38!�!6!) = 7.059.052

2. Beispiel: Genau 2 aufeinanderfolgende Lottozahlen
12111000000000000000000000000000000000000000 entspricht immer eineindeutig den Lottozahlen 1, 3, 4, 6, 8, 10. Es gibt hier immer 39 Nullen, 4 Einsen und 1 Zwei.
Anzahl der Permutationen mit Wiederholung: 44! / (39!�4!�1!) = 5.430.040

3. Beispiel: 3 und 2 aufeinanderfolgende Lottozahlen
00200000010000000000000000000000000000000003 entspricht immer eineindeutig den Lottozahlen 3, 4, 12, 47, 48, 49. Es gibt hier immer 41 Nullen, 1 Eins, 1 Zwei und 1 Drei.
Anzahl der Permutationen mit Wiederholung: 44! / (41!�1!�1!�1!) = 79.464

Auch die Wahrscheinlichkeit P, dass bei einer Ziehung der kleinste Abstand zwischen den Lottozahlen genau k betr�gt, kann berechnet werden.
Dabei bedeutet k=1, dass mindestens zwei aufeinanderfolgende Lottozahlen gezogen werden. Es gilt:

k=1: P = ((49 6) � (44 6)) / (49 6) = 6.924.764 / 13.983.816 = 1 : 2,0194 = 49,5198%
k=2: P = ((44 6) � (39 6)) / (49 6) = 3.796.429 / 13.983.816 = 1 : 3,6834 = 27,1487%
k=3: P = ((39 6) � (34 6)) / (49 6) = 1.917.719 / 13.983.816 = 1 : 7,2919 = 13,7139%
k=4: P = ((34 6) � (29 6)) / (49 6) = 869.884 / 13.983.816 = 1 : 16,0755 = 6,2207%
k=5: P = ((29 6) � (24 6)) / (49 6) = 340.424 / 13.983.816 = 1 : 41,0776 = 2,4344%
k=6: P = ((24 6) � (19 6)) / (49 6) = 107.464 / 13.983.816 = 1 : 130,1256 = 0,7685%
k=7: P = ((19 6) � (14 6)) / (49 6) = 24.129 / 13.983.816 = 1 : 579,545 = 0,1725%
k=8: P = ((14 6) � (9 6)) / (49 6) = 2919 / 13.983.816 = 1 : 4790,62 = 0,0209%
k=9: P = (9 6) / (49 6) = 84 / 13.983.816 = 1 : 166.474 = 0,0006%

Herleitung: Beispiel: Kleinster Abstand zwischen den Lottozahlen betr�gt genau 3.

Bei den folgenden zwei Beispielen betr�gt der kleinste Abstand der Lottozahlen mindestens 3:
10, 20, 23, 30, 40, 49
10, 20, 25, 30, 40, 49
In allen solchen F�llen kann man die Abst�nde zwischen den Lottozahlen jeweils um 2 verkleinern, ohne dass zwei Lottozahlen zusammenfallen.
Dazu muss man die zweite Lottozahl um 2, die dritte Lottozahl um 4 usw. und schlie�lich die sechste Lottozahl um 10 erniedrigen.
Man erh�lt dann folgende Lottozahlen:
10, 18, 19, 24, 32, 39
10, 18, 21, 24, 32, 39
6 Lottozahlen, die die oben genannte Bedingung erf�llen, lassen sich also immer eindeutig auf 49 � 5�2 = 39 Lottozahlen abbilden.
Und daf�r gibt es genau (396) = 3.262.623 Kombinationen.

Das Entsprechende macht man dann f�r 6 Lottozahlen, bei denen der kleinste Abstand mindestens 4 betr�gt. Hier muss man die Abst�nde jeweils um 3 verkleinern.
Die eindeutige Abbildung erfolgt jetzt auf 49 � 5�3 = 34 Lottozahlen und es gibt hierf�r genau (346) = 1.344.904 Kombinationen.
Die Differenz (396) � (346) = 1.917.719 ist somit die Anzahl der Kombinationen f�r 6 Lottozahlen, bei denen der kleinste Abstand genau 3 betr�gt.

Weitere Berechnungen zu Wahrscheinlichkeiten beim Lotto findet man auf der Lotto-Seite.

Beispiel 22 (Lotto 6 aus 49 - mindestens eine gleiche Zahl bei zwei verschiedenen Ziehungen)

Wie gro� ist die Wahrscheinlichkeit, dass bei zwei Ziehungen von Lotto 6 aus 49 mindestens eine Zahl gleich ist?

Herleitung:
Die Wahrscheinlichkeit, dass die erste Zahl der zweiten Ziehung mit keiner der 6 Zahlen der ersten Ziehung �bereinstimmt, betr�gt 43/49.
Die Wahrscheinlichkeit, dass die ersten beiden Zahlen der zweiten Ziehung mit keiner der 6 Zahlen der ersten Ziehung �bereinstimmen, betr�gt (43/49) · (42/48).
Die Wahrscheinlichkeit, dass keine der 6 Zahlen der zweiten Ziehung mit einer der 6 Zahlen der ersten Ziehung �bereinstimmt,
betr�gt deshalb (43/49) · (42/48) · (41/47) · (40/46) · (39/45) · (38/44) = 0,435965 = 43,5965%.

Die Wahrscheinlichkeit f�r mindestens eine gleiche Zahl bei zwei Ziehungen von Lotto 6 aus 49 ist also gleich 1 � 43,5965% = 56,4035%.

Weitere Berechnungen zu Wahrscheinlichkeiten beim Lotto findet man auf der Lotto-Seite.

Beispiel 23 (Kleinster Abstand zwischen aufeinanderfolgenden Geburtstagen)

Wie gro� ist im Mittel der kleinste Abstand zweier aufeinanderfolgender Geburtstage von 23 Sch�lern in einer Klasse? Wie gro� sind im Mittel die anderen Abst�nde?

Wenn die Anzahl der Sch�ler n = 23 betr�gt und wenn man die L�nge eines Jahres mit d = 365 Tagen annimmt, dann l�sst sich die mittlere L�nge g eines Abstandes durch die folgende Formel ausdr�cken, wobei k = 1 den kleinsten Abstand und k = n den gr��ten Abstand darstellt:

gn,d = d / n · ( Σi=1n (1/i) - Σi=1n-k (1/i) )

F�r die mittlere L�nge g der verschiedenen Abst�nde k ergibt sich dann:

  k   g (in Tagen)

  1     0,69
  2     1,41
  3     2,17
  4     2,96
  5     3,80
  6     4,68
  7     5,61
  8     6,60
  9     7,66
10     8,79
11   10,01
12   11,34
13   12,78
14   14,37
15   16,13
16   18,11
17   20,38
18   23,03
19   26,20
20   30,17
21   35,46
22   43,39
23   59,26

Im Mittel betr�gt also der kleinste Abstand zwischen zwei aufeinanderfolgenden Geburtstagen bei 23 Sch�lern nur 0,69 Tage oder etwas weniger als 17 Stunden.
Der gr��te Abstand ist im Mittel dagegen 59,26 Tage und somit knapp 2 Monate lang.

Beispiel 24 (Summe der Augenzahlen beim W�rfeln, Chance beim Kniffel-Spiel)

Wie gro� ist die Wahrscheinlichkeit, mit einem Wurf mit k=5 W�rfeln eine bestimmte Summe der Augenzahlen zu erzielen?
F�r die verschiedenen Summen n ergeben sich die folgenden Wahrscheinlichkeiten Pn (Berechnungen mit Hilfe eines Computer-Programms):

P5 = P30 = 1 / 7776 = 0,0129%
P6 = P29 = 5 / 7776 = 0,0643%
P7 = P28 = 15 / 7776 = 0,1929%
P8 = P27 = 35 / 7776 = 0,4501%
P9 = P26 = 70 / 7776 = 0,9002%
P10 = P25 = 126 / 7776 = 1,6204%
P11 = P24 = 205 / 7776 = 2,6363%
P12 = P23 = 305 / 7776 = 3,9223%
P13 = P22 = 420 / 7776 = 5,4012%
P14 = P21 = 540 / 7776 = 6,9444%
P15 = P20 = 651 / 7776 = 8,3719%
P16 = P19 = 735 / 7776 = 9,4522%
P17 = P18 = 780 / 7776 = 10,0309%

Diese Wahrscheinlichkeiten lassen sich auch mit der folgenden etwas umst�ndlichen Formel berechnen (m = Anzahl der Augenzahlen):

Pn = abs(Σi=0int((n-k)/m) (-1)i � (ki) � (n-m�i-1k-1)) / mk

Bei k=5 W�rfeln und m= 6 Augenzahlen bekommt man dann z.B. f�r die Augenzahlsumme n=12 folgende Wahrscheinlichkeit:

P12 = abs(Σi=0int(7/6) (-1)i � (5i) � (11-6�i4)) / 65 = abs(Σi=01 (-1)i � (5i) � (11-6�i4)) / 65 = abs((50) � (114) � (51) � (54)) / 65 = abs(330 � 25) / 65 = 305 / 7776

Mit steigender Anzahl m der W�rfel n�hert sich �brigens die Verteilung der Summe n der Augenzahlen immer mehr einer Gau�verteilung.

Die entsprechenden Wahrscheinlichkeiten f�r eine bestimmte Summe bei 3 W�rfen mit 5 W�rfeln (Chance beim Kniffel-Spiel) findet man auf der Kniffel-Strategie-Seite.

Bei einem Wurf mit k=3 W�rfeln gelten f�r eine bestimmte Summe der Augenzahlen folgende Wahrscheinlichkeiten:

P3 = P18 = 1 / 216 = 0,4630%
P4 = P17 = 3 / 216 = 1,3889%
P5 = P16 = 6 / 216 = 2,7778%
P6 = P15 = 10 / 216 = 4,6296%
P7 = P14 = 15 / 216 = 6,9444%
P8 = P13 = 21 / 216 = 9,7222%
P9 = P12 = 25 / 216 = 11,5741%
P10 = P11 = 27 / 216 = 12,5000%

Beispiel 25 (Anzahl unterschiedlich aussehender Perlenketten)

Wie viele M�glichkeiten Nn gibt es, mit n Perlen unterschiedlich aussehende offene bzw. ringf�rmige Ketten herzustellen,
wenn die n Perlen alle eine unterschiedliche Farbe besitzen?

Offene Ketten:

Nn = n! / 2 (f�r n > 1; N1 = 1)

Beispiele:
N1 = 1
N2 = 2! / 2 = 2 / 2 = 1
N3 = 3! / 2 = 6 / 2 = 3
N4 = 4! / 2 = 24 / 2 = 12
N5 = 5! / 2 = 120 / 2 = 60
N6 = 6! / 2 = 720 / 2 = 360
N7 = 7! / 2 = 5040 / 2 = 2520

Herleitung: Die Reihenfolge der Perlen von einem Ende aus betrachtet unterscheidet sich immer von der Reihenfolge vom anderen Ende aus betrachtet,
weil ja alle Perlen unterschiedliche Farben haben (au�er bei nur einer Perle, also n = 1).
Au�erdem ergibt sich eindeutig aus der einen Reihenfolge die gegenl�ufige Reihenfolge. Die Zuordnung ist also eineindeutig.
Die beiden Reihenfolgen bilden also ein Paar. F�r n Perlen unterschiedlicher Farbe gibt es n! verschiedene Reihenfolgen.
Da man die Kette umdrehen kann, gibt es also nur n!/2 unterschiedlich aussehende Ketten (f�r n > 1). F�r n = 1 gibt es nur eine Kette.

Ringf�rmige Ketten:

Nn = (n�1)! / 2 (f�r n > 2; N1 = 1; N2 = 1)

Beispiele:
N1 = 1
N2 = 1
N3 = (3�1)! / 2 = 2! / 2 = 2 / 2 = 1
N4 = (4�1)! / 2 = 3! / 2 = 6 / 2 = 3
N5 = (4�1)! / 2 = 4! / 2 = 24 / 2 = 12
N6 = (6�1)! / 2 = 5! / 2 = 120 / 2 = 60
N7 = (7�1)! / 2 = 6! / 2 = 720 / 2 = 360

Herleitung: Man kann jede der n Perlen als Anfangsperle betrachten. Deshalb gibt es bei jeder Kette in einer Richtung betrachtet n verschiedene Reihenfolgen,
weil ja jede Anfangsperle eine andere Farbe hat. Geht man bei jeder Anfangsperle in die andere Richtung, so bekommt man eine andere Reihenfolge,
weil die Perle nach der Anfangsperle jeweils eine andere Farbe hat, au�er f�r n = 1 und n = 2.
F�r n Perlen unterschiedlicher Farbe gibt es also n! / (2�n) = (n � 1)! / 2 unterschiedlich aussehende Ketten (f�r n > 2). F�r n = 1 und n = 2 gibt es nur eine Kette.

Wie viele M�glichkeiten Nn gibt es, mit n Perlen unterschiedlich aussehende offene bzw. ringf�rmige Ketten herzustellen,
wenn man f�r die Kette nur Perlen mit maximal zwei oder drei unterschiedlichen Farben verwenden darf?

Offene Ketten:

Maximal zwei unterschiedliche Farben:

Gerades n: Nn = (2n+2n/2)/2
Ungerades n: Nn = 2 · Nn-1 (f�r n > 1; N1 = 2)

Beispiele:
N1 = 2
N2 = 3
N3 = 6
N4 = 10
N5 = 20
N6 = 36
N7 = 72
N8 = 136
N9 = 272

Herleitung: Wenn man den beiden Farben die Ziffern 0 und 1 zuordnet, stellt eine offene Kette quasi eine Bin�rzahl dar. Mit n Perlen kann man also zun�chst
2n Bin�rzahlen erzeugen, wenn man von einem Ende der Kette ausgeht. Wenn man vom anderen Ende ausgeht, erh�lt man wieder die gleiche Anzahl von Bin�rzahlen.
Diese Bin�rzahlen sind den anderen Bin�rzahlen eineindeutig zugeordnet. Eine bestimmte Kette repr�sentiert also normalerweise alle darstellbaren Bin�rzahlen doppelt.
Die Anzahl unterschiedlich aussehender Ketten w�re also nur 2n/2. Das gilt allerdings nicht f�r spiegelsymmetrische Ketten, weil sich hier immer die gleiche
Bin�rzahl ergibt, egal, von welchem Ende man ausgeht. Bei geradem n gibt es 2n/2 solcher symmetrischer Ketten. Diese Anzahl h�tte man also nicht durch 2 dividieren d�rfen.
Man muss also zu 2n/2 noch 2n/2/2 addieren, um insgesamt die richtige Anzahl unterschiedlicher Ketten zu bekommen.
Alle Bin�rzahlen, bei denen das gerade n um 1 vergr��ert wird, bei denen also das n ungerade wird, erh�lt man z.B. dadurch, dass man in der Mitte eine 0 oder 1 einf�gt.
Dadurch verdoppelt sich nicht nur die Anzahl der Bin�rzahlen, sondern auch die Anzahl der symmetrischen Bin�rzahlen und damit auch die Anzahl unterschiedlich aussehender Ketten.

Maximal drei unterschiedliche Farben:

Gerades n: Nn = (3n+3n/2)/2
Ungerades n: Nn = 3 · Nn-1 (f�r n > 1; N1 = 3)

Ringf�rmige Ketten (Hierf�r gibt es keine einfachen Formeln.):

maximal zwei unterschiedliche Farben:

N1 = 2
N2 = 3
N3 = 4
N4 = 6
N5 = 8
N6 = 13
N7 = 18
N8 = 30
N9 = 46
N10 = 78
N11 = 126
N12 = 224

Maximal drei unterschiedliche Farben:

N1 = 3
N2 = 6
N3 = 10
N4 = 21
N5 = 39
N6 = 92
N7 = 198
N8 = 498
N9 = 1219
N10 = 3210
N11 = 8418
N12 = 22913

Beispiel 26 (kreisf�rmige Diskussionsgruppe)

Eine Diskussionsgruppe mit n Personen sitzt auf St�hlen in einem Kreis. Nach einer Pause werden die Personen per Zufall neu auf die n St�hle verteilt.
Wie gro� ist die Wahrscheinlichkeit Pn, dass alle Personen zwei neue Sitznachbarn bekommen?

F�r n Personen betr�gt die Wahrscheinlichkeit:

P3 = 0 / 6 = 0 / 1 = 0,000%
P4 = 0 / 24 = 0 / 8 = 0,000%
P5 = 10 / 120 = 1 / 12 = 8,333%
P6 = 60 / 720 = 5 / 60 = 8,333%
P7 = 462 / 5040 = 33 / 360 = 9,167%
P8 = 3920 / 40.320 = 245 / 2520 = 9,722%
P9 = 36.954 / 362.880 = 2053 / 20.160 = 10,184%
P10 = 382.740 / 3.628.800 = 19.137 / 181.440 = 10,547%
P11 = 4.327.510 / 39.916.800 = 196.705 / 1.814.400 = 10,841%
P12 = 53.088.888 / 479.001.600 = 2.212.037 / 19.958.400 = 11,083%

Die Wahrscheinlichkeit Pn, dass alle Personen einen neuen linken (rechten) Sitznachbar bekommen, betr�gt: Pn = (!n � (�1)n) / n! (Beispiel: P7 = (1854 + 1) / 5040) = 36,806%)

Anhang

n = Anzahl der Ziehungen
m = Anzahl der erfolgreichen Ziehungen
n - m = Anzahl der erfolglosen Ziehungen
k = Anzahl der Kugeln
r = Anzahl der "richtigen" Kugeln
k - r = Anzahl der "falschen" Kugeln
p = r/k = Wahrscheinlichkeit f�r eine erfolgreiche Ziehung

Hypergeometrische Verteilung (Ziehung ohne Zur�cklegen):

Pn,m = (rm) · (k�rn�m) / (kn)

Binomialverteilung (m << r; n - m << k - r; n << k) (gilt nur f�r Ziehung mit Zur�cklegen):

Pn,m = (nm) · pm · (1�p)n�m

Varianz: n·p·(1�p)

Herleitung aus hypergeometrischer Verteilung:
Pn,m = (rm) · (k�rn�m) / (kn)
= r! · (k�r)! · n! · (k�n)! / (m! · (r�m)! · (n�m)! · ((k�r)�(n�m))! · k!)
= (n! / (m! · (n�m)!) · (r! / (r�m)!) · ((k�r)! / ((k�r)�(n�m))!) · ((k�n)! / k!)
= (nm) · rm · (k�r)n�m · k�n

Poissonverteilung�(m << n; p << 1):

Pn,m = ((n·p)m / m!) · e�n·p

Herleitung aus Binomialverteilung:
Pn,m = (nm) · pm · (1�p)n�m
= (n!/(m!·(n�m)!)) · (pm / (1�p)m) · (1�p)n
= (nm/m!) · (p/(1�p))m · 1/(1+p)n

Gau�verteilung (m gro�, n gro�):

Pn,m = (1/(σ·√(2·π))) · e�x2/2

x = (m�n·p) / σ
Varianz: σ2 = n·p

Herleitung aus Poissonverteilung:
Pn,m = ((n·p)m / m!) · e�n·p
= (n·p/m)m · em / √(2·π·m) · e�n·p

ε = (m�n·p) / (n·p) = m/(n·p) � 1
m / (n·p) = 1 + ε
m = n·p · (1 + ε)

Pn,m = (1 + ε)-m · em�n·p / √(2·π·(1 + ε)·n·p)
= 1 / √(2·π·(1 + ε)·n·p) · e�m·ln(1 + ε) + m � n·p
= 1 / √(2·π·n·p) · e�n·p·(1 + ε)·(ε � ε2/2) + n·p + n·p·ε � n·p

Stirlingsche Formel (gilt schon f�r kleine n in guter N�herung; ihre Abweichung ist ab 9! kleiner als 1%.):

n! = (n/e)n · √(2·π·n)

Geordneter Zufall und harmonische Reihe

Wenn man im Intervall von 0 bis 1 insgesamt n-1 Zufallszahlen erzeugt, so entstehen in diesem Intervall zwischen den Zufallszahlen n Teilintervalle. Wiederholt man diesen Vorgang viele Male mit jeweils neuen Zufallszahlen und bildet die Mittelwerte der jeweiligen Intervalle zwischen 0 und der kleinsten Zufallszahl, zwischen der kleinsten und zweitkleinsten Zufallszahl usw., dann sind alle Mittelwerte gleich gro� und betragen 1/n.

Ordnet man jedoch die entstehenden Teilintervalle nach ihrer Gr��e und bildet dann die Mittelwerte (Erwartungswerte) der jeweils kleinsten, zweitkleinsten usw. Teilintervalle, dann betr�gt die mittlere Gr��e gn,k des k-ten Teilintervalls:

gn,k = 1/n · Σi=n+1-kn (1/i) = 1/n · ( Σi=1n (1/i) - Σi=1n-k (1/i) )

Man kann die mittlere L�nge der Intervalle also als die durch n dividierte Differenz zweier harmonischer Reihen ausdr�cken.
Die folgende Zusammenstellung zeigt die Ergebnisse f�r eins bis sechs Intervalle:

Ein Intervall: g1,1 = 1
Zwei Intervalle: g2,1 = 1/4; g2,2 = 3/4
Drei Intervalle: g3,1 = 1/9; g3,2 = 5/18; g3,3 = 11/18
Vier Intervalle: g4,1 = 1/16; g4,2 = 7/48; g4,3 = 13/48; g4,4 = 25/48
F�nf Intervalle: g5,1 = 1/25; g5,2 = 9/100; g5,3 = 47/300; g5,4 = 77/300; g5,5 = 137/300
Sechs Intervalle: g6,1 = 1/36; g6,2 = 11/180; g6,3 = 37/360; g6,4 = 57/360; g6,5 = 87/360; g6,6 = 147/360

F�r gro�e n gilt in guter N�herung: Σi=1n (1/i) = ln(n) + Eulersche Konstante
Daraus folgt: gn,k = 1/n · (ln(n) - ln(n-k)) = 1/n · (ln(n) - ln(n · (1-k/n))) = 1/n · (ln(n) - ln(n) - ln(1-k/n)) = -1/n · ln(1-k/n)

Normiert man diese bis n laufende Funktion auf den Bereich von 0 bis 1 und setzt x = k/n, so ergibt sich die Funktion f(x) = -ln(1-x).
Durch die Normierung wird aus der Summe der L�nge aller Intervalle die Fl�che unter der Funktion f(x) mit dem Fl�cheninhalt 1.
Das Intervall mit der mittleren L�nge 1/n liegt bei der Funktion an der Stelle, wo f(x) = 1 ist.
Also gilt: -ln(1-x) = 1; ln(1-x) = -1; eln(1-x) = e-1; 1-x = 1/e.
Es sind also 1/e = 36,787944% aller Intervalle gr��er als das mittlere Intervall der L�nge 1/n.

F�r das Integral der Funktion f(x) gilt: Integral(-ln(1-x)) dx = x + (1-x) · ln(1-x) + C.
Die Summe der L�ngen aller Intervalle oberhalb des Intervalls mit der mittleren L�nge ist demnach:
[x + (1-x) · ln(1-x)]1-1/e1 = 1 - (1-1/e) - 1/e · ln(1/e) = 1/e + 1/e = 2/e.
Die Intervalle, die gr��er sind als das Intervall der mittleren L�nge 1/n, haben also zusammen 2/e = 73,575888% der Gesamtl�nge 1.

Die Summe der L�nge aller Intervalle ist f�r die gr��ere H�lfte aller Intervalle entsprechend:
[x + (1-x)·ln(1-x)]1/21 = 1 - 1/2 - 1/2 · ln(1/2) = 1/2 + 1/2 · ln(2).
Die Intervalle, die zur gr��eren H�lfte geh�ren, haben also zusammen 1/2 + 1/2 · ln(2) = 84,657359% der Gesamtl�nge 1.

Das Intervall, unterhalb dessen die Summe der L�ngen aller Intervalle 1/2 betr�gt, liegt an der Stelle x,
die die L�sung der Gleichung x + (1-x) · ln(1-x) = 1/2 darstellt.
Die L�sung l�sst sich nur numerisch berechnen und betr�gt 0,81331769.
Es haben damit 18,668231% der gr��ten Intervalle zusammen die Gesamtl�nge 1/2.

Copyright � Werner Brefeld, 2002 ... 2023

Wie berechnet man die Anzahl von Kombinationen?

Was ist K in der Kombinatorik?

Wie berechnet man n über k?

Wie viele Möglichkeiten bei 4 Variablen?