Someone wrote n letters to different people, sealed them in…

Someone wrote $n$ letters to different people, sealed them in envelopes, and then wrote the $n$ different addresses on the envelopes at random. Determine the probability that at least one letter will be correctly addressed.

Step 1: The model

The addresses form a random permutation of $n$ items; all $n!$ are equally likely. $A_i$ = "letter $i$ is correctly addressed".

Step 2: Inclusion–exclusion

\[ P\Big(\sum_iA_i\Big)=\sum_iP(A_i)-\sum_{i\lt j}P(A_iA_j)+\sum_{i\lt j\lt k}P(A_iA_jA_k)-\dots \]

Step 3: The terms

For $k$ given letters, the probability that all are correct is $\frac{(n-k)!}{n!}$ (the other $n-k$ letters may go anywhere). There are $\binom nk$ choices, so the $k$-th sum equals

\[ \binom nk\frac{(n-k)!}{n!}=\frac{1}{k!}. \]

Step 4: The answer

\[ \boxed{P=1-\frac1{2!}+\frac1{3!}-\dots+(-1)^{n+1}\frac1{n!}=\sum_{k=1}^{n}\frac{(-1)^{k+1}}{k!}.} \]

Step 5: The limit

Since $e^{-1}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}$,

\[ P\ \to\ 1-\frac1e\approx0.6321 \qquad (n\to\infty). \]

Already for $n=5$ the probability is practically $1-\frac1e$. Surprisingly, the answer hardly depends on the number of letters: with $10$ letters or $1000$ letters, about $63\%$ of the time at least one letter is correct.

Step 6: Check for $n=3$

The $6$ permutations of $1,2,3$: $123$ (3 correct), $132$, $213$, $321$ (1 correct each), $231$, $312$ (none). At least one correct: $4$ of $6$, i.e. $\frac23=1-\frac12+\frac16$ ✓.