Everything Goes Wrong

Let $d(x)$ be the number of derangements of length $x$ , the ways to deliver $x$ letters so that none of them is delivered correctly.

Let's say we have $n$ letters. We first look at person $1$ .

Person $1$ has $n-1$ choices for the letter he gets. Let's say he gets letter $k$ . Now, if we look at person $k$ , there are 2 possibilities.

Case 1: He gets person $1$ 's letter. We can remove person $1$ and $k$ and now have $d(n-2)$ .

Case 2: He doesn't get person $1$ 's letter. Now, we can pretend like that letter was letter $k$ since person $k$ can't get it and we have $d(n-1)$ .

Thus, we create the recursion: $d(n)=(n-1)(d(n-1)+d(n-2))$

It can be seen that $d(1)=0$ and $d(2)=1$ .

Using the recursion above, we have:

$d(3)=2(1+0)=2$

$d(4)=3(2+1)=9$

$d(5)=4(9+2)=44$

$d(6)=5(44+9)=265$

$d(7)=6(265+44)=\boxed{1854}$

Derangement 7