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\) ?
[ For example, the needed inclusion-exclusion formula is given in Problem 12, p. 31 in Pitman]
You will also need to know the number of elements in the set
\[ \{ (i_1,i_2,\cdots, i_k) : 1 \leq i_1 < i_2 < \cdots < i_k\leq n\} \]
which is discussed here.
