# Derangements

**Derangements** are arrangements of some number of objects into positions such that no object goes to its specified position. In the language of permutations, a derangement is a permutation \( \sigma\) of \( n\) elements with no fixed point, that is: \( \sigma(i) \ne i \) for all \( i \in \{1,2,\ldots,n\} \).

## Formulae

Let \(D(n)\) be the number of derangements for \(n\) different objects, then \[ D_n=n!\displaystyle\sum_{r=0}^{n} \dfrac{(-1)^r}{r!}.\ _\square \]

Let there be \(n\) distinct objects with their \(n\) distinct respective positions. Then the number of derangements is \(n!-N,\) where \(N\) is the number of ways of arranging the \(n\) objects in such a way that at least one object goes to its right position.

To find \(N\), use PIE.

Let \(A_r\) be the set of permutations in which the \(r^\text{th}\) object goes into its right position. The goal is to find \(\displaystyle N=\left|\bigcup_{r=1}^{n} A_r\right|\).

Observe that \(|A_i|=(n-1)!\), \(|A_i \cap A_j|=(n-2)!,\) and so on.

Then \(\displaystyle\sum_{i}|A_i|=\binom{n}{1}(n-1)!\), \(\displaystyle\sum_{i<j}|A_i \cap A_j|=\binom{n}{2}(n-2)!,\) and so on.

Now, using PIE,\[\begin{align} N=\left|\displaystyle\bigcup_{r=1}^{n} A_r \right| &=\sum \lvert A_{i_1} \rvert-\sum_{i < j} \lvert A_{i} \cap A_{j} \rvert +\cdots+(-1)^{n+1} \left|A_1 \cap A_2 \cap \cdots \cap A_n\right|\\ &=\sum_{r=1}^{n}(-1)^{r+1} \binom{n}{r}(n-r)! \\ &=\sum_{r=1}^{n} (-1)^{r+1} \dfrac{n!}{r!}. \end{align}\]

Therefore, the number of derangements is

\[\begin{align} D_n&=n!-N\\ &=n!-\sum_{r=1}^{n} (-1)^{r+1} \dfrac{n!}{r!}\\ &=n!\displaystyle\sum_{r=0}^{n} \dfrac{(-1)^r}{r!}. \ _\square \end{align}\]

The above formula can be rewritten recursively as

\(D(n)=nD(n-1)+ (-1)^n. \)

In how many different ways can you rearrange the letters in the word MONKEY such that no letter in the new arrangement is in the same place as in the original word? (I.e. NOKEYM wouldn't work since O would be in the same place as it was in MONKEY.)

##### For more Permutations quizzes

Check out my other problems

Note that \( D_n/n! \) is the \(n^\text{th}\) partial sum of the Taylor series for \( e^x \) evaluated at \( x=-1\), so \[ \lim_{n\to\infty} \frac{D_n}{n!} = \frac1{e}. \]

So for large \( n \), the probability that a permutation of \( n \) objects is a derangement is approximately \( \frac1{e}\).

In fact for any positive integer \(n,\) \(D_n=\left[\frac{n!}{e}\right],\) where the square brackets are the nearest integer function.

Here is another recursive formula for \( D(n)\):

\[ D(n) = (n-1)(D(n-1)+D(n-2)). \]

Let \(a, b, c, \ldots, n\) be \(n\) distinct objects with their respective containers \(A, B, C, \ldots, N,\) and suppose \(a\) goes into \(B.\) Then it gives rise to the following two cases:

Case 1: When \(b\) goes to \(A:\)

Leaving out \(a\) and \(b,\) there are derangements for \(n-2\) objects: \(D(n-2).\)

Case 2: When \(b\) goes to any other container:

Leaving out \(a,\) the number of these is the same as the number of derangements of \(n-1\) objects (including \(b\)): \(D(n-1).\)

(If \( c \) goes to \( B \) in the derangement of \( n-1\) objects, this corresponds to the derangement of \( n \) objects where \( c\) goes to \( A \) and \( a \) goes to \( B \).)Thus, the total is \(D(n-1)+D(n-2).\)

But the original assumption was that \(a\) goes to \(B\). There are \( n-1\) choices for \( B\), so \[ D(n)=(n-1)(D(n-1)+D(n-2)). \ _\square \]

## Examples

## Mickey the mailman is very lazy. He has received 10 parcels to 10 different people. However, because he is lazy, he doesn't bother reading the address and delivers them off randomly. In how many ways can Mickey deliver the parcels such that no one gets the right parcel?

By the derangements formula, the number of derangements possible is

\[\begin{align} 10! \left ( \frac{1}{0!} - \frac{1}{1!} + \cdots + \frac{1}{10!} \right )&= 10! - 10! + \frac{10!}{2!} - \cdots + 1\\ &= 1334961. \end{align}\]

Therefore, there are a total of 1334961 ways to deliver the parcels such that no one gets the right parcel.