Combinatorics

Section 9.1 Derangements

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 sibling 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, \ldots, n\}\text{,}\) and think of a derangement as a bijection

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

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

Case 2: \(\boldsymbol{f(j) = n}\) for some \(\boldsymbol{j \neq i}\text{.}\) In this case, we define another function

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

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

We also need some initial conditions. We have \(D_1=0\text{;}\) there is no way of arranging a single object so that it doesn't end up in the correct place. Also, \(D_2=1\text{,}\) 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.