Derangements

Consider a the finite set $A = \{ 1, 2, ..., n \}$ of positive integers from $1$ to $n$. The most natural permutation of this set is the permutation $(1, 2, ..., n)$ in which we do not change the ascending order of the positive integers. Suppose that we want to count the number of permutations $(x_1, x_2, ..., x_n)$ of the positive integers in $A$ such that each number $x_i \neq i$ for $i \in \{1, 2, ..., n \}$ in these permutations. In other words, we want to count the number of permutations $(x_1, x_2, ..., x_n)$ such that the first number in the permutation is not $1$, the second number in the permutation is not $2$, …, and the $n^{\mathrm{th}}$ number in the permutation in $n$.

For example, if $A = \{1, 2, 3, 4\}$ then the permutation $(2, 3, 4, 1)$ is a derangement of elements in $A$. The permutation $(3, 2, 4, 1)$ is not a derangement of elements in $A$ because when we compare $(3, 2, 4, 1)$ with $(1, 2, 3, 4)$ we see that the second number in the permutation $(3, 2, 4, 1)$ is $2$.

For a more applicable example, suppose that we consider the word $CAKE$ and we want to determine how many permutations there are of the letters in this word such that the first letter is not $C$, the second letter is not $A$, the third letter is not $K$ and the fourth letter is not $E$.

For example, the permutation $KEAC$ is a derangement of $CAKE$, however, the permutation $CKEA$ is not a derangement of $CAKE$ since the first letter of $CKEA$ is $C$.

We will now define these special types of permutations.

Definition: If $A = \{1, 2, ..., n \}$ is a finite $n$-element set of ascending positive integers then a Derangement of the elements in $A$ is a permutation $(x_1, x_2, ..., x_n)$ of these elements such that $x_i \neq i$ for all $i \in \{ 1, 2, ..., n \}$. The number of derangements of $A$ is denoted by $D_n$.

If $A = \{ 1 \}$ then there is only $1!$ permutation of elements in $A$, namely $(1)$ and so there are no derangements of $A$, i.e., $D_1 = 0$.

If $A = \{ 1, 2 \}$ then there are only $2!$ permutations of elements in $A$, namely $(1, 2)$ and $(2, 1)$ to which $(2, 1)$ is the only derangement of $A$ so $D_2 = 1$.

For small values of $n$ it is often easy to count the number of derangements $D_n$, however, it would be very useful to obtain a formula for $D_n$ for any positive integer $n$ we desire. The following theorem gives us that formula.

Theorem 1: The number of derangements $D_n$ of the $n$-element set of positive integers $A = \{1, 2, ..., n \}$ is given by $\displaystyle{D_n = n! \cdot \sum_{i=0}^{n} \frac{(-1)^i}{i!} = n! \left (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + ... + \frac{(-1)^n}{n!} \right )}$.

• Proof: Let $A = \{1, 2, ..., n \}$ be a finite $n$-element set of positive integers. Let $\mathcal A$ be the set of all $n$-permutations from $A$. For each $i \in \{1, 2, ..., n \}$ let $A_i \subseteq A$ be the set of permutations $(x_1, x_2, ..., x_i, ..., x_n)$ such that $x_i = i$. If a permutation $(x_1, x_2, ..., x_i, ..., x_n) \in A_i$ then $(x_1, x_2, ..., x_i, ..., x_n) = (x_1, x_2, ..., i, ..., x_n)$ and is not a derangement of the elements in $A$.

• If $D$ is the set of derangements of elements in $A$ then if $(x_1, x_2, ..., x_n) \in D$ then $(x_1, x_2, ..., x_n) \not \in A_i$ for all $i \in \{1, 2, ..., n \}$, that is:

(1)

\begin{align} \quad D = \mathcal A \setminus \{ A_1 \cup A_2 \cup ... \cup A_n \} = \mathcal A \setminus \bigcup_{i=1}^{n} A_i \end{align}

• Therefore we have that the number of derangements $D_n$ is given by:

(2)

\begin{align} \quad D_n = \mid D \mid = \biggr \lvert \mathcal A \setminus \bigcup_{i=1}^{n} A_i \biggr \rvert \end{align}

• We need to determine the number of elements in $\displaystyle{\biggr \lvert \bigcup_{i=1}^{n} A_i \biggr \rvert}$. We will achieve this using The Inclusion-Exclusion Principle. We have that:

(3)

\begin{align} \quad \biggr \lvert \bigcup_{i=1}^{n} A_i \biggr \rvert = \sum_{i=1}^{n} \lvert A_i \rvert - \sum_{1 \leq p_1 < p_2 \leq n} \lvert A_{p_1} \cap A_{p_2} \rvert + \sum_{1 \leq p_1 < p_2 < p_3 \leq n} \lvert A_{p_1} \cap A_{p_2} \cap A_{p_3} \rvert - ... + (-1)^{n+1} \sum_{1 \leq p_1 < p_2 < ... < p_n \leq n} \lvert A_{p_1} \cap A_{p_2} \cap ... \cap A_{p_n} \rvert \end{align}

• Now each permutation of $A_{1}$ is of the form $(x_1, x_2, ..., x_{i-1}, i, x_{i+1}, ..., x_n)$. There are thus $(n - 1)!$ of these permutations, i.e., $\mid A_i \mid = (n-1)!$ for all $i \in \{1, 2, ..., n \}$.

• Now for $i_1, i_2 \in \{1, 2, ..., n \}$ where $i_1 \neq i_2$ we have that $A_{i_1} \cap A_{i_2}$ is the set of permutations for which $x_{i_1} = i_1$ and $x_{i_2} = i_2$. There are thus $(n - 2)!$ of these permutations, i.e., $\mid A_{i_1} \cap A_{i_2} \mid = (n - 2)!$ for all $i_1, i_2 \in \{1, 2, ..., n \}$ where $i_1 \neq i_2$.

• For $i_1, i_2, i_3 \in \{1, 2, ..., n \}$ where $i_1 \neq i_2 \neq i_3$ we have that $A_{i_1} \cap A_{i_2} \cap A_{i_3}$ is the set of permutations for which $x_{i_1} = i_1$, $x_{i_2} = i_2$ and $x_{i_3} = i_3$. There are thus $(n - 3)!$ of these permutations.

• In general we see that for $i_1, i_2, ..., i_k \in \{1, 2, ..., n \}$ where $i_p \neq i_q$ for $p, q \in \{1, 2, ..., k \}$ that $\bigcap_{t=1}^{k} A_{i_t}$ is the set of permutations for which $x_{i_1} = i_1$, $x_{i_2} = i_2$, …, $x_{i_k} = i_k$. There are thus $(n - k)!$ of these permutations.

• Now we note that there are $\binom{n}{1} = n$ subsets $A_i$. Furthermore, there are $\binom{n}{2}$ subsets $A_{i_1} \cap A_{i_2}$ for $i_1, i_2 \in \{1, 2, ..., n \}$. In general there are $\binom{n}{k}$ subsets of the form $\bigcap_{t=1}^{k} A_{i_t}$ for $i_1, i_2, ..., i_k \in \{1, 2, ..., n \}$. Applying the Inclusion-Exclusion principle and we get that:

(4)

\begin{align} \quad \biggr \rvert \bigcup_{i=1}^{n} A_i \biggr \rvert = \binom{n}{1}(n - 1)! - \binom{n}{2}(n - 2)! + ... + (-1)^n \binom{n}{n-1} (1)! + (-1)^{n+1} \binom{n}{n} (0)! \\ \quad \biggr \rvert \bigcup_{i=1}^{n} A_i \biggr \rvert = \frac{n!}{1!(n-1)!} \cdot (n-1)! - \frac{n!}{2!(n-2)!} \cdot (n - 2)! + ... + (-1)^n \frac{n!}{(n-1)!1!} \cdot 1! + (-1)^{n+1} \frac{n!}{n! \cdot 0!} \cdot 0! \\\ \quad \biggr \rvert \bigcup_{i=1}^{n} A_i \biggr \rvert = n! - \frac{n!}{2!} + ... + (-1)^n \frac{n!}{(n-1)!} + (-1)^{n+1} \frac{n!}{n!} \end{align}

• Since $\bigcup_{i=1}^{n} A_i \subseteq \mathcal A$ we have that by the principle of subtraction that $\biggr \lvert \mathcal A \setminus \bigcup_{i=1}^{n} A_i \biggr \rvert = \mid \mathcal A \mid - \biggr \lvert \bigcup_{i=1}^{n} A_i \biggr \rvert$ and so:

(5)

\begin{align} \quad D_n = \biggr \lvert \mathcal A \setminus \bigcup_{i=1}^{n} A_i \biggr \rvert \\ \quad D_n = \mid \mathcal A \mid - \biggr \lvert \bigcup_{i=1}^{n} A_i \biggr \rvert \\ \quad D_n = n! - \left ( n! - \frac{n!}{2!} + ... + (-1)^n \frac{n!}{(n-1)!} + (-1)^{n+1} \frac{n!}{n!} \right ) \\ \quad D_n = n! \left (1 - \frac{1}{1!} + \frac{1}{2!} + ... + \frac{(-1)^n}{n!} \right ) \quad \blacksquare \end{align}