Answer to Question #303740 in Discrete Mathematics for Snave

Question

Write down all derangements of the set \left\{ a,b,c,d \right\} and show that the number of derangements is the same as predicted by the recurrence D(n) = (n - 1)(D(n - 2) + D(n - 1)) with initial values D(1) = 0 and D(2) = 1. Hint: a derangement is a permutation of an ordered set where no element is in the same place as before. Example: \left\{ b,a,d,c \right\} is a derangement of \left\{ a,b,c,d \right\} because all of the letters positions have changed.

Answer 1

There are nine derangements for the set $\{a,b,c,d\}$. The derangements are

$\left\{\{b,a,d,c\}, \{b,c,d,a\}, \{b,d,a,c\}, \{c,a,d,b\}, \{c,d,a,b\}, \{c,d,b,a\}, \{d,a,b,c\},\right.\\ \left. \{d,c,a,b\}, \{d,c,b,a\}\right\}.$

Given, $D(n) = (n-1)(D(n-2)+D(n-1))$ with $D(1) =0~ \& ~D(2) = 1$.

$\begin{aligned} D(4) &= (4-1)(D(2)+D(3))\\ &= 3(D(2) + 2(D(1)+D(2)))\\ &= 3(1+2)\\&=9\\ \end{aligned}$.

Thus, the number of derangements is the same as predicted by the recurrence relation.