Question

A person wrote n letters to n friends. He sealed the n letters in n envelopes. The next day he wrote addresses at random and sent the letters. Find the probability that at least one of his friends gets the correct letter.

Answer 1

We will say that a match occurs at position jif Xj=j. Thus, number of matches is the random variable N defined mathematically by

Nn=∑j=1nIj

where Ij=1(Xj=j) is the indicator variable for the event of match at position j. Our problem is to compute the probability distribution of the number of matches. This is an old and famous problem in probability that was first considered by Pierre-Remond Montmort; it sometimes referred to as Montmort's matching problem in his honor.

Now let's consider the case of real interest, when the sampling is without replacement,