Question: Tanya prepared 4 different letters to be sent to 4 different addresses. For each letter she prepared an envelope with its correct address. If the 4 letters are to be put in 4 envelopes at random, what is the probability that no letter will be put into the envelope with its correct address?
My attempt: (I know you can do this question with the derangement formula, but I wish to know why my following argument fails).
Call the 4 letters, $L_1$, $L_2$, $L_3$, $L_4$ and call the 4 envelopes $e_1$, $e_2$, $e_3$, $e_4$. I "visualize" the question like this:
where I have to put $L_1$ through to $L_4$ in the empty slots where the subscripts are all different. Clearly there are $4!$ number of ways to put 4 letters in the 4 slots above. Now I need to count the number of ways with the restriction that all subscripts are all different between the $L$'s and $e$'s. So clearly, for $e_1$ there are 3 options, we can have either $L_2$, $L_3$, or $L_4$. Say we put $L_2$ into $e_1$. Now, there's $L_1$, $L_3$, $L_4$ left, meaning there are 3 options for $e_2$, say we put $L_1$ into $e_2$, now there's $L_3$ and $L_4$ left, $L_4$ must go in $e_3$ and $L_3$ must go in $e_4$, so there's 1 option for $e_3$ and 1 option for $e_4$. Thus, there are $3*3*1*1 = 9$ ways. So the probability is $9/24$, which is the correct answer.
However, why does this following argument not work? Again, we have three options for $e_1$, but this time, let's put in $L_3$ in $e_1$ (rather than $L_2$ like the argument above). So now we have $L_1$, $L_2$, and $L_4$ left, clearly $L_2$ can't go into $e_2$, so there's 2 options for $e_2$, namely, $L_1$ and $L_4$. Say we pick $L_1$ for $e_2$, same as the argument above, there's 1 option left for $e_3$ and 1 option for $e_4$. In this way, we have $3*2*1*1 = 6$ ways. Why is this wrong?
Best Answer
In your second argument, if you put $L_4$ in $e_2$, then you have two options to put the last two letters in the last two envelopes, instead of just one. So, following your second line of reasoning, the formula becomes $3*(1+2)=9$.