Answer to Question #302918 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\}.$

Let $D(n)$ denote the number of derangements of n distinct objects.

For each derangement, let 1 be placed in position $i$ for $2\le i\le n$. We have two cases to consider.

Case 1: $i$ is in position 1

Then there are $D(n - 2)$ ways to derange the remaining $n-2$ integers. Since there are $n - 1$ choices for $i$ we have $(n-1)D(n-2)$ derangements.

Case 2: $i$ is not in position 1

Then there are $D(n-1)$ ways to derange the $n - 1$ integers by considering 1 as new natural position for $i$. Again with $n -1$ choices for $i$, we have $(n-1)D(n-1)$ derangements.

Hence, $D(n) = (n-1)(D(n-2)+D(n-1))$ with $D(1) =0~ \& ~D(2) = 1$, since there are no derangements possible for 1 object and exactly one derangement for 2 objects.

Now, $D(4) = (4-1)(D(2)+D(3)) = 3(D(2) + 2(D(1)+D(2))) = 3(1+2)=9$.

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

Note: Book for reference is "DISCRETE AND COMBINATORIAL MATHEMATICS - An Applied Introduction - FIFTH EDITION by RALPH P. GRIMALDI".