A postman has to deliver four letters to four different houses in a street. Unfortunately the rain has erased the addresses, so he just distributes them randomly, one letter per house. What is the probability that every house gets the right letter? (☆ What is the probability that every house gets a wrong letter?)
This was a problem I stumbled on to while revising combinatorics. For the first part it is pretty straightforward, as for four houses, say $A, B, C$ and $D$, there are $4$ letters $L_A, L_B, L_C$ and $L_D$, and only one combination exists such that the correct letter is delivered to the correct house. However, for the starred question, my logic goes as follows, but the answer quite doesn't agree with what the site says.
My logic :
Let the houses $A, B, C$ and $D$ be side by side in the same order as they appear in the alphabet.
$A$ $B$ $C$ $D$
X_______________
X marks the location of the postman. At house $A$, out of the four letters $L_A, L_B, L_C$, and $L_D$, there exist only three possibilities such that house $A$ gets the wrong letter. For house $B$, two exist and for house $C$ only $1$ possibility, either of the remaining $2$ letters. The last house is guaranteed to have received the wrong letter provided the above conditions hold true. Therefore the possibilities are $3 \cdot 2 \cdot 1 = 6$. Therefore the probability is $6 / 24 = 1 / 4 = 0.25$
However the site says (quoted exactly from https://mathigon.org/world/Combinatorics#:~:text=To%20find%20the%20probability%20that,called%20the%20Inclusion%20Exclusion%20principle.)
To find the probability that every letter gets delivered to the wrong house is a bit more difficult. It is not simply $1 – 0.0417$, since there are many cases in which one or two, but not all houses get the right letter. In this simple case, the easiest solution would be to write down all $24$ possibilities. You will find that in $9$ out of the $24$ cases every house gets a wrong letter, which gives a probability of $0.375 = 37.5\%$. If there more too many houses to write down all possibilities, you can use an idea called the Inclusion Exclusion principle.
Can someone explain the loophole in my logic, because the solution on the site asks us to bruteforce which happens to be a very frowned upon technique in exams?
The number of ways the postman can deliver a wrong letter to house $B$ depends on what has already occurred. If he has delivered letter $L_B$ to house $A$, then there are three ways to deliver an incorrect letter to house $B$ since it is no longer possible to deliver the correct letter to house $B$. On the other hand, if letter $L_B$ has not already been delivered to house $A$, then there are only two ways to deliver an incorrect letter to house $B$ since letter $L_B$ is still available. Similarly, if letter $L_C$ has been delivered to either house $A$ or house $B$, then there are two ways to deliver an incorrect letter to house $C$ since it is no longer possible to deliver the correct letter to house $C$. On the other hand, if letter $L_C$ has not been delivered to either house $A$ or house $B$, then there is only one way to deliver an incorrect letter to house $C$ since letter $L_C$ is still available.
Addendum: I described ways in which your method leads to an undercount. What fcz's excellent answer shows is that you may be counting arrangements which are not derangements at all.
Solution: There are $4!$ ways for the postman to deliver four distinct letters to four different houses. To find the number of derangements, we must exclude those permutations in which at least one letter is delivered to the correct house. There are $\binom{4}{k}$ to select $k$ houses which receive the correct letter and $(4 - k)!$ to deliver one letter each to the remaining houses. Hence, by the Inclusion-Exclusion Principle, the number of ways the postman can deliver each letter to a different house so that no person receives a correct letter is $$\sum_{k = 0}^{4} (-1)^k\binom{4}{k}(4 - k)! = 4! - \binom{4}{1}3! + \binom{4}{2}2! - \binom{4}{3}1! + \binom{4}{4}0! = 9$$ Hence, the probability that no person receives a correct letter is $$\frac{1}{4!} \sum_{k = 0}^{4} (-1)^k\binom{4}{k}(4 - k)! = \frac{4! - \binom{4}{1}3! + \binom{4}{2}2! - \binom{4}{3}1! + \binom{4}{4}0!}{4!} = \frac{9}{24} = \frac{3}{8}$$ In general, the number of derangements of $n$ objects is $$\sum_{k = 0}^{n} (-1)^k\binom{n}{k}(n - k)!$$ Hence, the probability that no person receives the correct letter is $$\frac{1}{n!}\sum_{k = 0}^{n} (-1)^k\binom{n}{k}(n - k)! = \sum_{k = 0}^{4} (-1)^k \frac{1}{n!} \cdot \frac{n!}{k!(n - k)!} \cdot (n - k)! = \sum_{k = 0}^{n} \frac{(-1)^k}{k!}$$ For large values of $n$, this is approximately $1/e$. See derangements for further information.