Skip to main content

Section 3.3 Application: Derangements

Video: Derangements

Recall that the permutations of a set \(S\) are the bijective functions from \(S\) to itself. We have a special name for those permutations that leave no element fixed:

Definition 3.3.1. Derangement.

A derangement is a permutation on \(\{1,2,\ldots,n\}\) such that no element is mapped to itself.

The permutation on \(\{1,2,3\}\) that takes \(1\) to \(3\text{,}\) \(2\) to \(1\text{,}\) and \(3\) to \(2\) is a derangement; we can also denote it as the string 312.

There are only two derangements on \(\{1,2,3\}\text{:}\) 231 and 312.

The permutation 3241 on \(\{1,2,3,4\}\) is not a derangement since 2 is sent to itself. We call 2 a fixed point of the permutation.

(Try listing all derangements of \(\{1,2,3,4\}\text{.}\))

Exploration 3.3.1. Deriving \(D_n\).

Count the number of derangements \(D_n\) of the set \(\{1,2,\ldots,n\}\) using Theorem 3.2.6, by following these steps:

(a)

Define \(A_i\) to be the set of permutations of \(\{1,2,\ldots,n\}\) for which \(i\) is a fixed point. (There are no restrictions on the other elements; there may be other fixed points.)

Then, express \(D_n\) as the cardinality of a set involving the \(A_i\)'s.

(b)

If \(S \subseteq \{1,2,\ldots,n\}\) with \(|S| = k\text{,}\) find a formula for \(\left|\displaystyle\bigcap_{i \in S} A_i\right|\text{.}\)

(c)

Combine with Theorem 3.2.6 to derive a formula for \(D_n\text{,}\) then fill in the statement of the result below.

Remark 3.3.4.

For problems where it is relevant, you may leave your answers in terms of \(D_n\text{.}\) (You don't have to compute exact values unless asked.)

Evaluate \(D_4\) and verify that it is the correct number by listing all derangements of \(\{1,2,3,4\}\text{.}\)

Using a computer, evaluate the ratio

\begin{equation*} \frac{D_n}{n!} \end{equation*}

of derangements to all permutations of \(\{1,2,\ldots,n\}\) for \(n\) increasingly large.

Verify that the ratios approach the value of \(\frac{1}{e}\text{.}\)