2. Vertauschte Briefe
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, \ldots, n\} fragen.
n = 1:
Wenn wir nur einen Brief und einen Umschlag haben, können wir nichts falsch machen:
Die gesuchte Wahrscheinlichkeit ist also 0.n = 2:
Hier gibt es zwei Möglichkeiten, die Wahrscheinlichkeit ist 1/2.n = 3:
Wir betrachten die sechs möglichen Permutationen:
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1 (kein Brief im richtigen Umschlag)
3, 1, 2 (kein Brief im richtigen Umschlag)
3, 2, 1
Nur in zwei der sechs Permutationen liegt kein Brief im richtigen Umschlag.
Die Wahrscheinlichkeit ist also 1/3.
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:
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.
A_k sei die Menge aller Permutationen,
bei denen der k-te Brief im richtigen Umschlag steckt.
Dann ist
P_{\ge 1}(n) = \lvert A_1 \cup A_2 \cup \ldots \cup A_n \rvert
die Anzahl der Permutationen, bei denen mindestens ein Brief im richtigen Umschlag steckt.
Nach dem Prinzip der Ein- und Ausschließung ist daher
P_{\ge 1}(n) = \sum_{i=1}^n \lvert A_i \rvert
- \sum_{1\le i<j\le n} \lvert A_i \cap A_j \rvert
+ \green{\displaystyle\sum_{1\le i<j<k\le n} \lvert A_i \cap A_j \cap A_k \rvert}
- \ldots \pm \lvert \bigcap_{i=1}^n A_i \rvert
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:
\blue{\displaystyle{n \choose 3}}\;\ocher{(n-3)!}
= \blue{\displaystyle{\frac{n!}{3! (n-3)!}}}\;\ocher{(n-3)!} = \green{\displaystyle{\frac{n!}{3!}}}
Ebenso ergeben sich die übrigen Terme:
P_{\ge 1}(n) = \frac{n!}{1!}
- \frac{n!}{2!} + \green{\displaystyle{\frac{n!}{3!}}} - \ldots \pm \frac{n!}{n!}
= \sum_{k=1}^n (-1)^{k-1} \frac{n!}{k!}
Damit ist die Anzahl der Möglichkeiten, bei denen alle Briefe im falschen Umschlag stecken
P_0(n) = n! - P_{\ge 1}(n) = \sum_{k=0}^n (-1)^k \frac{n!}{k!}
= \sum_{k=2}^n (-1)^k \frac{n!}{k!}
Die Wahrscheinlichkeit dafür, dass alle Briefe im falschen Umschlag stecken, ist also
\pink{\displaystyle{\frac{P_0(n)}{n!}}} = \sum_{k=2}^n \frac{(-1)^k}{k!}
Die Wahrscheinlichkeit konvergiert mit n.
Das erkennt man mit der Reihenentwicklung der Exponentialfunktion:
\begin{aligned}
e^x & = \sum_{n=0}^\infty \frac{x^n}{n!} \cr
\pink{\displaystyle{e^{-1}}} & = \sum_{n=0}^\infty \frac{(-1)^n}{n!}
= \sum_{n=2}^\infty \frac{(-1)^n}{n!}
= \pink{\displaystyle{\lim_{n\to\infty}\frac{P_0(n)}{n!}}}
\end{aligned}
Der Grenzwert für die Wahrscheinlichkeit, dass alle Briefe im falschen Umschlag stecken, ist demnach:
