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

Question

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.

Answer 1

There are not $2!$ ways to organize the lat two letters. There is only $1$ way. Because the second way of organizing them would be to put them in their correct envelopes, which wouldn't match up with the constraint of having exactly $3$ letters getting sent correctly.

A similar mistake was made in the second problem.

To find the number of ways no letters get put in the correct envelope, also known as finding the number of derangements, start by taking $5!$ and subtract off all the cases letter $1$ is in the correct spot, then letter $2$, letter $3$, etc. Then use the inclusion exclusion principle

Answer 2

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.

Answer 3

The strategy here follows the inclusion/exclusion principle. For each subset of the letters, we ask how many ways there are to put those letters in the correct envelopes, if we don't care what happens to the other letters. That's an easy question to answer; if it's $k$ letters we want to put in the right place, then the remaining $5-k$ letters can go in the remaining $5-k$ envelopes in $(5-k)!$ ways.

So, suppose we want to put letters A and B in the correct envelopes, while the remaining letters C, D, and E go in the wrong envelopes. Well, we start with our count $(5-2)!=6$ ways to put A and B in the right places. Now, we need to subtract off the cases in which more than just those two went in the right envelopes - that's $(5-3)!=2$ ways to put A, B, and C in the right envelopes, $(5-3)!=2$ ways for ABD, and $(5-3)!=2$ ways for ABE. We're now down to zero - but we've overshot. If four letters ABCD went in the right envelopes, we subtracted that twice instead of once - so we add that $(5-4)!=1$ way back, and the same with ABCE and ABDE. Back up to 3 - and we've overshot again. In the case that all five letters are in the right place, we've added in too many copies, and we need to subtract one to get it back in balance. That drops us to the final answer of two ways. Multiply by the ten ways to choose two of the five letters to be those that we place correctly, and the answer to question (2) is $\boxed{20}$.

That's how inclusion/exclusion works - when we can cleanly count how many ways to do at least a certain number of things, we count how many ways to do exactly a certain number of things with this alternating sum over subsets that include our base. I'll leave running the details on question (3) as an exercise; it's all the same principles, just larger.

Note that this particular problem, of permutations that don't fix anything, is worked in that Wikipedia article (for any size). It's well known, as the derangement problem.