# Kombinatorik

## 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, ..., 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:

    # 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

P_{\ge 1}(n) = | A_1 \cup A_2 \cup \ldots \cup A_n |

die Anzahl der Permutationen, bei denen mindestens ein Brief im richtigen Umschlag steckt.

Nach dem Prinzip der Ein- und Ausschließung ist daher

\def\green{\bbox[#c0ffc0,2pt]} P_{\ge 1}(n) = \sum_{i=1}^n \left| A_i \right| - \sum_{1\le i<j\le n} \left| A_i \cap A_j \right| + \green{\sum_{1\le i<j<k\le n} \left| A_i \cap A_j \cap A_k \right|} - \ldots \pm \left| \bigcap_{i=1}^n A_i \right|

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:

\def\blue{\bbox[#c0e0ff,2pt]} \def\ocher{\bbox[#ffe0a0,2pt]} \def\green{\bbox[#c0ffc0,2pt]} \blue{n \choose 3} \ocher{(n-3)!} = \blue{\frac{n!}{3! (n-3)!}} \ocher{(n-3)!} = \green{\frac{n!}{3!}}

Ebenso ergeben sich die übrigen Terme:

\def\green{\bbox[#c0ffc0,2pt]} P_{\ge 1}(n) = \frac{n!}{1!} - \frac{n!}{2!} + \green{\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

\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{eqnarray} e^x & = & \sum_{n=0}^\infty \frac{x^n}{n!} \cr e^{-1} & = & \sum_{n=0}^\infty \frac{{-1}^n}{n!} = \sum_{n=2}^\infty \frac{{-1}^n}{n!} = \lim_{n\to\infty}\frac{P_0(n)}{n!} \end{eqnarray}

Der Grenzwert für die Wahrscheinlichkeit, dass alle Briefe im falschen Umschlag stecken, ist demnach:

    exp(-1)