[Math] Envelope Question: Five letters addressed to individuals 1-5 are randomly placed in five addressed envelopes, one letter in each envelope.

combinatoricsinclusion-exclusionprobability

I'm trying to find the probability of:

  1. Exactly three letters go in the correct envelopes.
  2. Exactly two letters go in the correct envelopes
  3. No letters go in the correct envelopes

Here is my approach:

So there is clearly a total of 5! distinct ways of arranging the letters.

  1. If exactly three letters go in the correct envelopes, then there are $5 \choose 3$ ways of choosing the positions for the three correct envelopes, and for the remaining two letters, there are 2! ways of organizing them. Thus, probability = $\frac{{5 \choose 3} \cdot 2!}{5!}$.

  2. If exactly two letters go in the correct envelopes, then there are $5 \choose 2$ ways of choosing the positions for the two correct envelopes, and for the remaining three letters, there are 3! ways of organizing them. Thus, probability = $\frac{{5 \choose 2} \cdot 3!}{5!}$.

  3. I'm not really sure how to approach this problem.

Any input would be great.

Best Answer

Note the use of the word exactly. You did not take that into account.

Probability that exactly three letters are placed in the correct envelopes

There are indeed $\binom{5}{3}$ ways to select which three letters are placed in the correct envelopes. That leaves two envelopes in which to place the remaining two letters. Those letters must each be placed in the other envelope, which can only be done in one way. Hence, the probability that exactly three letters go in the correct envelopes is $$\frac{1}{5!} \cdot \binom{5}{3}$$

Probability that exactly two letters are placed in the correct envelopes

There are $\binom{5}{2}$ ways to select which two letters are placed in the correct envelopes. None of the remaining letters go in the correct envelopes. There are just two ways to do this. \begin{align*} &\color{red}{1}, \color{red}{2}, \color{red}{3}\\ &\color{red}{1}, 3, 2\\ &2, 1, \color{red}{3}\\ &2, 3, 1\\ &3, 1, 2\\ &3, \color{red}{2}, 1 \end{align*} Hence, there are $\binom{5}{2} \cdot 2$ favorable cases.

We can use the Inclusion-Exclusion Principle to see why.

There are $3!$ ways to permute the three letters. From these, we must subtract those cases in which at least one letter is placed in the correct envelope.

There are three ways to select a letter to be placed in the correct envelope and $2!$ ways to place the remaining letters.

There are $\binom{3}{2}$ ways to select two letters to be placed in the correct envelopes and $1!$ ways to place the remaining letter.

There are $\binom{3}{3}$ ways to select three letters to be placed in the correct envelopes and $0!$ ways to place the (nonexistent) remaining letters.

By the Inclusion-Exclusion Principle, the number of ways to place the remaining three letters so that none of them is placed in the correct envelope is $$3! - \binom{3}{1}2! + \binom{3}{2}1! - \binom{3}{3} = 6 - 6 + 3 - 1 = 2$$ as claimed.

Therefore, the probability that exactly two letters are placed in the correct envelopes is $$\frac{1}{5!} \cdot 2\binom{5}{2}$$

Probability that none of the letters is placed in the correct envelopes

This is a derangement problem. An Inclusion-Exclusion arguments shows that the number of ways of placing none of the five letters in its correct envelope is

$$5! - \binom{5}{1}4! + \binom{5}{2}3! - \binom{5}{3}2! + \binom{5}{4}1! - \binom{5}{5}0!$$

Dividing that number by $5!$ gives the desired probability.