The matching problem

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.

  1. Find the probability that at least one letter is put in a correctly addressed envelope. [Hint: use the inclusion-exclusion formula.]
  2. 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.


Comments are closed.