n Briefe werden mit verbundenen Augen in ihre n Umschläge gesteckt. Wie groß ist die Wahrscheinlichkeit, dass dabei kein Brief in den richtigen Umschlag kommt?
Wenn Sie es etwas abstrakter mögen, können Sie auch nach dem Anteil der fixpunktfreien Abbildungen unter allen bijektiven Abbildungen auf der Menge {1, 2, ..., n} fragen.
Bevor Sie weiter lesen, schätzen Sie bitte einmal, wie groß die Wahrscheinlichkeit ist, dass bei einer Million Briefen keiner im im richtigen Umschlag steckt!
Für einige weitere kleine n überlassen wir mathGUIde das sture Überprüfen aller Permutationen:
# Anteil der Permutationen von 0, 1, ..., n-1, # in denen keine Zahl auf sich selbst abgebildet wird. def alleVertauscht(n): r = fromTo(0, n-1) falsche = [all([i != p[i] for i in r]) for p in permutations(r)] return falsche.count(True) / factorial(n) # Test für n = 1, 2, ..., 8: printValueTable( [ (lambda n: "{0}%".format(100*alleVertauscht(n)), "alle Vertauscht")], "n", 1, 8, 1)
Die Tabelle drängt die Vermutung auf, dass die Wahrscheinlichkeit sehr
schnell gegen einen Wert von ungefähr 0.3679 konvergiert.
Dass diese Vermutung richtig ist, wollen wir uns nun klarmachen.
Ak sei die Menge aller Permutationen,
bei denen der k-te Brief im richtigen Umschlag steckt.
Dann ist
die Anzahl der Permutationen, bei denen mindestens ein Brief im richtigen Umschlag steckt.
Nach dem Prinzip der Ein- und Ausschließung ist daher
Den grün unterlegten Term können wir so berechnen: 3 Briefe (i, j, k) aus n Briefen auswählen (und in die richtigen Umschläge stecken), die n-3 übrigen Briefe beliebig verteilen:
Ebenso ergeben sich die übrigen Terme:
Damit ist die Anzahl der Möglichkeiten, bei denen alle Briefe im falschen Umschlag stecken
Die Wahrscheinlichkeit dafür, dass alle Briefe im falschen Umschlag stecken, ist also
Die Wahrscheinlichkeit konvergiert mit n. Das erkennt man mit der Reihenentwicklung der Exponentialfunktion:
Der Grenzwert für die Wahrscheinlichkeit, dass alle Briefe im falschen Umschlag stecken, ist demnach:
exp(-1)