A Recurrence Relation for the Derangement Numbers

A Recurrence Relation for the Derangement Numbers

On the Estimating the Number of Derangements of Elements from a Finite Set we saw that the number of derangements $D_n$ of a finite $n$-element set of positive integers $A = \{1, 2, ..., n \}$ can be approximated with the formula:

(1)
\begin{align} \quad D_n \approx n! \cdot e^{-1} \end{align}

We will now show that the derangement numbers $D_n$ can be defined be a recurrence relation.

Theorem 1: Let $A = \{ 1, 2, ..., n \}$ be a finite $n$-element set of positive integers. Then the number of derangements, $D_n$ of $A$ can be obtained by $D_n = (n - 1)(D_{n-1} + D_{n-2})$ for all $n \geq 3$.
  • Proof: Let $A = \{1, 2, ..., n \}$ be a finite $n$-element set of positive integers. Let $n \geq 3$. Let $D$ be the set of derangements of $A$. For each $i \in \{2, ..., n \}$ let $A_i \subset D$ be the set of derangements where $x_1 = i$. There are $n - 1$ subsets $A_2, A_3, ..., A_n$ that form a partition of all of the derangements $D$, that is $D = \cup_{i=2}^{n} A_i$ and $A_i \cap A_j = \emptyset$ for all $i, j \in \{ 2, 3, ..., n$ where $i \neq j$. Note that the number of derangements of elements from $A$ that start with $i$ is equal to the number of derangements of elements from $A$ that start with $j$ for all $i, j \in \{2, 3, ..., n \}$, that is, for some $\phi$ (dependent on $n$) we have $\mid A_i \mid = \mid A_j \mid = d (n)$ for all $i, j \in \{2, 3, ..., n \}$.
  • By the addition principle we have:
(2)
\begin{align} \quad D_n = \mid D \mid = \biggr \rvert \bigcup_{i=2}^{n} A_i \biggr \rvert = \sum_{i=2}^{n} \mid A_i \mid = (n - 1) \phi \end{align}
  • Now each of these groups of $\phi$ many derangements can be further categorized. Arbitrarily consider the subset $A_2 \subset D$. The derangements in $A_2$ for $x_2 \neq 2$, $x_3 \neq 3$, …, $x_n \neq n$ are of the form:
(3)
\begin{equation} (2, x_2, x_3, ..., x_n) \end{equation}
  • For each of these derangements we consider two cases - the subset $A_2' \subset A_2$ of derangements where $x_2 = 1$ and the subset $A_2'' \subset A_2$ of derangements where $x_2 \neq 1$ so that:
(4)
\begin{align} \quad \phi = \mid A_2' \mid + \mid A_2'' \mid \end{align}
  • We first consider $A_2'$. We have that $x_2 = 1$ and so derangements in $A_2'$ for $x_3 \neq 3$, $x_4 \neq 4$, …, $x_n \neq n$ are of the form:
(5)
\begin{align} \quad (2, 1, x_3, ..., x_n) \end{align}
  • For the set $\{3, 4, ..., n \}$, the number of ways in which $x_3 \neq 3$, $x_4 \neq 4$, …, $x_n \neq n$ is the same number of ways in which we have for the set $\{1, 2, ..., n-2 \}$ that $x_1 \neq 1$, $x_2 \neq 2$, …, $x_{n-2} \neq n-2$. Therefore $\mid A_2' \mid = D_{n-2}$.
  • We now consider $A_2''$. We have that $x_2 \neq 1$ and so derangements in $A_2''$ for $x_2 \neq 1$, $x_3 \neq 3$, $x_4 \neq 4$, …, $x_n \neq n$ are of the form:
(6)
\begin{align} \quad (2, x_2, x_3, ..., x_n) \end{align}
  • For the set $\{1, 3, 4, ..., n \}$, the number of ways in which $x_2 \neq 1$, $x_3 \neq 3$, …, $x_n \neq n$ is the same number of ways in which we have for the set $\{1, 2, ..., n-1 \}$ that $x_1 \neq 1$, $x_2 \neq 2$, …, $x_{n-1} \neq n-1$. Therefore $\mid A_2'' \mid = D_{n-1}$.
  • We thus obtain that $\phi = D_{n-1} + D_{n-2}$ and so:
(7)
\begin{align} \quad D_n = (n - 1)\phi \\ \quad D_n = (n - 1)(D_{n-1} + D_{n-2}) \quad \blacksquare \end{align}

The recurrence relation for the derangement numbers $D_n$ can actually be simplified further as we see in the following corollary.

Corollary 1: Let $A = \{ 1, 2, ..., n \}$ be a finite $n$-element set of positive integers. Then the number of derangements, $D_n$ of $A$ can be obtained by $D_n = nD_{n-1} + (-1)^{n-2}$ for all $n \geq 3$.
  • Proof: From Theorem 1 we have that for all $n \geq 3$:
(8)
\begin{align} \quad D_n = (n - 1)(D_{n-1} + D_{n-2}) \\ \quad D_n = nD_{n-1} + nD_{n-2} - D_{n-1} - D_{n-2} \\ \quad D_n - nD_{n-1} = -(D_{n-1} - (n-1)D_{n-2}) \end{align}
  • We recursively simplify the righthand side of the equation above to get:
(9)
\begin{align} \quad D_n - nD_{n-1} = (-1)^2(D_{n-2} - (n-2)D_{n-3}) \\ \quad D_n - nD_{n-1} = (-1)^3(D_{n-3} - (n-3)D_{n-4}) \\ \quad \quad \vdots \quad \quad \quad \quad \quad \quad \\ \quad D_n - nD_{n-1} = (-1)^{n-2}(D_2 - 2D_1) \end{align}
  • Since $D_1 = 0$ and $D_2 = 1$ we get:
(10)
\begin{align} \quad D_n - nD_{n-1} = (-1)^{n-2} \\ \quad D_n = nD_{n-1} + (-1)^{n-2} \quad \blacksquare \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License