9.1: Derangements

Definition: Derangements

A derangement of a list of objects is a permutation of the objects, in which no object is left in its original position.

A classic example of this is a situation in which you write letters to ten people, address envelopes to each of them, and then put them in the envelopes, but accidentally end up with none of the letters in the correct envelope.

Another example might be a dance class in which five brother-sister pairs are enrolled. The instructor mixes them up so that no one is dancing with a sibling.

Since we’re considering enumeration, it shouldn’t surprise you that the question we want answered is: in how many ways can this happen? That is, given \(n\) objects, how many derangements of the \(n\) objects are there? Let’s use \(D_n\) to denote the number of derangements of \(n\) objects.

We can label the objects with the numbers \(\{1, . . . , n\}\), and think of a derangement as a bijection

\[f : \{1, . . . , n\} → \{1, . . . , n\}\]

such that \(f\) does not fix any value. There are \(n − 1\) choices for \(f(n)\), since the only restriction is \(f(n) \neq n\). Say \(f(n) = i\). We consider two possible cases.

Case 1: \(f(i) = n\)

Now, on the other \(n − 2\) values between \(1\) and \(n\) that are neither \(i\) nor \(n\), \(f\) must map \(\{1, . . . , n −1\} \setminus \{i\}\) to \(\{1, . . . , n −1\} \setminus \{i\}\), and must be a derangement. So there are \(D_{n−2}\) derangements that have \(f(n) = i\) and \(f(i) = n\).

Case 2: \(f(j) = n\) for some \(j \neq i\)

In this case, we define another function

\[g : \{1, . . . , n − 1\} → \{1, . . . , n − 1\}\]

as follows. We set \(g(j) = i\), and for every other value, \(g(a) = f(a)\) (that is, for every \(a ∈ \{1, . . . , n − 1\} \setminus \{j\}\)). We had \(f(j) = n\) and\( f(n) = i\), and we are eliminating \(n\) from the derangement while maintaining a bijection, by creating the shortcut \(f\) with \(g(j) = i\) but \(g(a) = f(a)\) for every other \(a ∈ \{1, . . . , n − 1\}\). Since \(f\) is a derangement and \(j \neq i\), we see that \(g\) is also a derangement (this time of \(n − 1\) objects). So there are \(D_{n−1}\) possible derangements \(g\), and for a fixed choice of \(i\), these are in one-to-one correspondence with derangements \(f\) that have \(f(j) = n\) and \(f(n) = i\), so there are also \(D_{n−1}\) of these.

We conclude that \(D_n = (n − 1)(D_{n−1} + D_{n−2})\).

We also need some initial conditions. We have \(D_1 = 0\); there is no way of arranging a single object so that it doesn’t end up in the correct place. Also, \(D_2 = 1\), since there is exactly one way of deranging two objects (by interchanging them).

If we wanted to solve this recursively-defined sequence, we would need to use exponential generating functions, which we’ll introduce in this chapter but won’t really study in this course. Instead, we’ll give the explicit formula for \(D_n\) without proof.

Proposition \(\PageIndex{1}\)

For any \(n ≥ 1\), the number of derangements of \(n\) objects is

\[D_n = n! \left( \sum_{i=0}^{n} \dfrac{(-1)^i}{i!} \right) \]

Exercise \(\PageIndex{1}\)

1. Use induction to prove Proposition 9.1.1.
2. Which kind of induction did you have to use to prove Proposition 9.1.1?
3. Calculate \(D_5\) using the explicit formula given in Proposition 9.1.1.
4. Calculate \(D_5\) using the recursive relation.