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,…,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 Dn.

Count the number of derangements Dn of the set {1,2,…,n} using Theorem 3.2.6, by following these steps:

🔗
(a)

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

Then, express Dn as the cardinality of a set involving the Ai's.

🔗
(b)

If S⊆{1,2,…,n} with |S|=k, find a formula for |⋂i∈SAi|.

🔗
(c)

Combine with Theorem 3.2.6 to derive a formula for Dn, 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 Dn. (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{.}\)