Irresponsible Mailman

The simplest way to solve this problem is to count the number of ways to deliver the letters with none delivered correctly, and then divide it by the number of ways to deliver the letters without any additional condition (except that it's one letter per residence).

The number of ways to deliver the letters is simply given by the number of permutations of 4 objects. This is $4! = 4 \cdot 3 \cdot 2 \cdot 1$ . The first residence can get any of the four letters, then the second residence can get any of the three remaining letters, then the third residence can get any of the remaining two letters, and the last residence gets the last letter. All choices are independent (there's no way to get the same way of delivering the letters by picking different choices), so we can use the rule of product to multiply the number of choices from each, giving the factorial above. So there are 24 ways to deliver the letters.

Now, to count the number of ways with none delivered correctly, we can count it in a careful case-by-case basis. Let the residences be A, B, C, D.

Residence A needs a letter other than letter A. There are three such choices; without loss of generality, let's assume it's letter B. (The other cases will be identical.)

Now look at residence B. It can receive any of the three available letters (because letter B has gone to residence A). There are three such choices, but interestingly, all of these will give exactly one possible way:

• If residence B gets letter A, then residence C must get letter D and residence D must get letter C. The other way around will leave both of them getting their own letters.
• If residence B gets letter C, then look at residence D. The available letters are letters A and D, so residence D must get letter A. This leaves residence C with letter D.
• If residence B gets letter D instead, we can look at residence C, which needs to get letter A, and thus residence D gets letter C.

In all three cases, we have one possible way. Thus the number of ways to send these letters is $3 \cdot 3$ ; 3 choices for residence A, and 3 choices for the residence whose letter goes to A. None of them gives the same way, so again, we can multiply them, giving 9 ways.

Finally, because all 24 ways are possibly likely and we want 9 of them, the probability is just 9 out of 24: $\frac{9}{24} = \boxed{\frac{3}{8}}$ .

---

A way to arrange $n$ objects so that none of them remains in their original position is also known as a derangement . Counting the number of derangements of $n$ objects, also known as $D_n$ , is best given by the following recurrence formula:

• $D_0 = 1, D_1 = 0$
• $D_n = (n-1) (D_{n-1} + D_{n-2})$ for $n \ge 2$

The reason for that last formula is that there are $n-1$ choices to put which object goes to the first position. Suppose object number $i$ goes there. Now, there are two cases:

• The first object goes to position $i$ . Then there are $n-2$ objects remaining, none of them should be in their original positions. This is given by $D_{n-2}$ .
• The first object doesn't go to position $i$ . Then there are $n-1$ objects remaining. Each of them has one forbidden position (their original positions, except for the first object which is position $i$ ), and each position has one forbidden object. This is essentially just a derangement on $n-1$ objects, even though it looks different. (If it helps, you can imagine the first object to be renamed as the $i$ -th object.) Now there are $D_{n-1}$ ways to do that.

The two cases are exhaustive and mutually exclusive, so we can use the rule of sum to add them together: $D_{n-1} + D_{n-2}$ ways for every choice of what object goes to the first position. And this choice is independent, so we can use the rule of product to multiply them together: $(n-1)(D_{n-1} + D_{n-2})$ derangements of $n$ objects.

Note that the same recurrence formula also applies for the factorials, only with different starting values: $0! = 1, 1! = 1$ , and $n! = (n-1)((n-1)! + (n-2)!)$ .

First of all, the number of ways to deliver the 4 letters (correctly or not) is:

4! = 24.

Then, we will determine, how many ways are there to deliver at least 1 of the letters.

The ways to deliver exactly:

• 4 letters correctly is 1

• 3 letters correctly is 0 (if letters a, b, c are delivered to houses A, B, C correctly, the remaining letter will be d and the remaining house D, meaning all letters are correctly delivered, not just 3)

• 2 letters correctly (the other two are mixed up with each other) is a choice of 2 out of 4: ${ 4 \choose 2} = \frac {4!}{2! × 2!} = 6$

• just 1 letter correctly: if we assume, that the correctly delivered letter is a, and the other 3 should have been delivered in the order of bcd, then we have 2 completely wrong ways: cdb and dbc. Since we can choose the correctly delivered letter 4 ways, the total number of cases is 4 × 2 = 8.

Therefore, the total number of ways, when none of the letters were delivered correctly is:

24 - (1 + 0 + 6 + 8) = 24 - 15 = 9 ,

and its probability is:

$\frac {9}{24}= \boxed { \frac {3}{8} }$

The answer is $\frac{!4}{4!}$ where !n is the number of derangements for $n$ different objects. $\frac{!4}{4!} = \frac{9}{24} =\boxed{\frac{3}{8}}$ Interesting to note that as $n$ approaches infinity, $\frac{!n}{n!} \rightarrow \frac{1}{e}$