Derangement

A derangement is a permutation with no fixed points. That is, a derangement of a set leaves no element in its original place. For example, the derangements of $\{1,2,3\}$ are $\{2, 3, 1\}$ and $\{3, 1, 2\}$ , but $\{3,2, 1\}$ is not a derangement of $\{1,2,3\}$ because 2 is a fixed point.

Notation and formula

The number of derangements of an $n$ -element set is called the $n$ th derangement number or rencontres number, or the subfactorial of $n$ and is sometimes denoted $!n$ or $D_n$ . (Note that using this notation may require some care, as $a!b$ can potentially mean both $(a!)b$ and $a(!b)$ .) This number satisfies the recurrences

$!n = n \cdot !(n - 1) + (-1)^n$

and

$!n = (n - 1)\cdot (!(n - 1) + !(n - 2))$

and is given by the formula

$!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.$

For example, the number derangements of a 3-element set is $3! \cdot \sum_{k = 0}^3 \frac{(-1)^k}{k!} = 6\cdot\left(\frac{1}{1} - \frac{1}{1} + \frac{1}{2} - \frac{1}{6}\right) = 2$ , which we know to be correct.

The first few derangements, starting from $n=0$ , are $1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, \ldots.$

Proof

This can be proven by using PIE. First, you take $n!$ , which represents all arrangements of the whole sequence. Then, you must subtract all arrangements in which each element appears in its original location, and now you have $n!-\binom{n}{1}(n-1)!$ . Then, you must add back in permutations in which each set of two elements stay in their original positions, as we subtracted them twice. Now, we have $n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!$ . PIE continues to give us this pattern. We have to alternate between subtracting and adding.

Now, we can change the form of $\binom{n}{k}(n-k)!$ . This is written as $\frac{n!}{k!(n-k)!}\times(n-k)!=\frac{n!}{k!}$ . We can now write our relation as $n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+...+(-1)^n(\frac{n!}{n!})$ . We can factor out $n!$ and get $n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!})=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$ .