The Matching Problem/Derangements - n letters to n people

There are n letters addressed to n eople at different addresses. The n addresses are typed on n envelopes. A disgruntled secretary shuffles the letters and puts them in the envelopes in random order, one letter per envelope.

Find the probability that at least one letter is put in a correctly addressed envelope. [Hint: use the inclusion-exclusion formula.] What is the probability approximately, for large n ?

My attempt at a solution:

$P(\text{all correct}) = \frac{1}{n!}$

$P(\text{$n-1$ correct}) = {n \choose n-1} \frac{1}{n!} = \frac{1}{1!(n-1)!}$, since ${n \choose n-1}$ ways of selecting n-1 correct letters.

$P(\text{$n-2$ correct}) = {n \choose n-2} \frac{1}{n!} = \frac{1}{2!(n-2)!}$

$\ldots$

$P(\text{$n-n$ correct}) = {n \choose n-n} \frac{1}{n!} = \frac{1}{n!(n-n)!} = \frac{1}{n!}$

This all looks ok to me, but I tested this for a case of 4 people, (I think the theoretical value should be $\frac{9}{24}$ but obviously that is not what I got. Can someone correct my logic please? Also, with regards to the hint about inclusion/exclusion - where would that come in?

I read about derangements on Wikipedia but it did not make total sense to me (the derivation).

I would appreciate any advice whatsoever including references to other material.

Solution 1:

Let $S$ be a subset of the letters. We denote by $f(S)$ the number of arrangements in which all of the letters of $S$ (and possibly some others) all get in the correct envelope.

Clearly $f(S)=(n-|S|)!$

Using inclusion exclusion the number of arrangements with at least one correct letter is :

$\sum\limits _{i=1}^n\binom{n}{i}(n-i)!(-1)^{i+1}=\sum\limits_{i=1}^n\frac{n!}{i!}=n!\sum_{i=1}^{n}\frac{-1^{i+1}}{i!}$. Therefore the fraction of arrangements that are derangements is $\sum_{i=1}^{n}\frac{-1^{i+1}}{i!}$ which approaches $\frac{e-1}{e}$ as $n$ goes to infinity.