Recurrence Relation for the Number of Derangements on a Finite Set

Theorem

The number of derangements $D_n$ on a finite set $S$ of cardinality $n$ is:

$D_n = \left({n - 1}\right) \left({D_{n-1} + D_{n-2}}\right)$

where $D_1 = 0$, $D_2 = 1$.

Proof

First note that $D_1 = 0$ because if $S = \left\{{s}\right\}$ (i.e. $\left|{S}\right| = 1$), then $f \left({s}\right) = s$ is the only permutation on $S$, and is not a derangement.

If $S = \left\{{s, t}\right\}$, then there are two permutations on $S$:

• $f = \left\{{\left({s, s}\right), \left({t, t}\right)}\right\}$; and
• $g = \left\{{\left({s, t}\right), \left({t, s}\right)}\right\}$,

and only the latter is a derangement.

So $D_2 = 1$.

Now, let $f: S \to S$ be a derangement. We aim to count the total number of such $f$.

Without loss of generality, we can take $S = \left\{{1, 2, \ldots, n+1}\right\}$.

Now, consider an arbitrary $s \in S$ such that $s \neq 1$, and set $f \left({s}\right) = 1$.

By the sum rule for counting, the total number of $f$ will be:

( the number of $f$ where $f(1) \neq s$ ) + ( the number of $f$ where $f(1)=s$ ).

Case 1

$f(1) \ne s$

Take $T_1=\{1,2,\ldots ,s-1,s+1, \ldots, n+1\}=S\setminus\{s\}$ and define the derangement $g_1:T_1 \to T_1$ by $g_1(t) = f(t)$ $\forall t \in T_1$.

Then $g_1$ is a derangement on a set of order $n,$ and so there are $D_n$ such $g_1$.

Note that $f=g_1\cup f(s)$.

Since $s$ can be chosen in $n$ ways, by the product rule for counting there are in total $nD_n$ such $f$ where $f(s) \neq 1$.

Case 2

$f(1) = s$

Take $T_2=\{2,3,\ldots ,s-1,s+1, \ldots, n+1\}=S\setminus\{1,s\}$ and define the derangement $g_2:T_2 \to T_2$ by $g_2(t) = f(t)$ $\forall t \in T_2$.

Then $g_2$ is a derangement on a set of order $n-1$, and so there are $D_{n-1}$ such $g_2$.

Note that $f=g_2\cup \{s\} \cup f(s)$. Since $s$ can be chosen in $n$ ways, by the product rule for counting there are in total $nD_{n-1}$ such $f$ where $f(s) = 1$.

Summing the results from both cases, we get the total number of derangements $f$ on a set of order $n+1$ is $D_{n+1} = n D_n + nD_{n-1} = n(D_n+D_{n-1})$ as desired.

$\blacksquare$