7.4: Derangements
- Page ID
- 97900
Now let's consider a situation where we can make use of the properties defined in Example 7.5. Fix a positive integer n and let X denote the set of all permutations on \([n]\). A permutation \(\sigma \in X\) is called a derangement if \(\sigma(i) \neq i\) for all \(i=1,2,…,n\). For example, the permutation \(\sigma\) given below is a derangement, while \(\mathcal{τ}\) is not.
If we again let \(P_i\) be the property that \(\sigma(i)=i\), then the derangements are precisely those permutations which do not satisfy \(P_i\) for any \(i = 1,2,...,n\).
For each subset \(S \subseteq [n]\), \(N(S)\) depends only on \(|S|\). In fact, if \(|S|=k\), then
\(N(S) = (n-k)!\)
- Proof
-
For each \(i \in S\), the value \(\sigma(i)=i\) is fixed. The other values of \(\sigma\) are a permutation among the remaining \(n−k\) positions, and there are \((n−k)!\) of these.
As before, the principal result of this section follows immediately from the lemma and the Principle of Inclusion-Exclusion.
For each positive integer \(n\), the number \(d_n\) of derangements of \([n]\) satisfies
\(d_n = \displaystyle \sum_{k=0}^n (-1)^k \dbinom{n}{k}(n-k)!\).
For example,
\[\begin{align*} d_5 &= \dbinom{5}{0}5! - \dbinom{5}{1} 4! + \dbinom{5}{2}3! - \dbinom{5}{3}2! + \dbinom{5}{4}1! - \dbinom{5}{5} 0! \\[4pt] &= 120 - 120 + 60 -20 +5 -1 \\[4pt] &= 44 \end{align*}\]
It has been traditional to cast the subject of derangements as a story, called the Hat Check problem. The story belongs to the period of time when men wore top hats. For a fancy ball, 100 men check their top hats with the Hat Check person before entering the ballroom floor. Later in the evening, the mischievous hat check person decides to return hats at random. What is the probability that all 100 men receive a hat other than their own? It turns out that the answer is very close to \(1/e\), as the following result shows.
For a positive integer \(n\), let \(d_n\) denote the number of derangements of \([n]\). Then
\(\displaystyle \lim_{n \to \infty} \dfrac{d_n}{n!} = \dfrac{1}{e}\).
Equivalently, the fraction of all permutations of \([n]\) that are derangements approaches \(1/e\) as \(n\) increases.
- Proof
-
It is easy to see that
\(\dfrac{d_n}{n!} = \dfrac{\sum_{k=0}^n(-1)^k \binom{n}{k}(n-k)!}{n!}\)
\(= \displaystyle \sum_{k=0}^n(-1)^k \dfrac{n!}{k!(n-k)!} \dfrac{(n-k)!}{n!}\)
\(= \displaystyle \sum_{k=0}^n (-1)^k \dfrac{1}{k!}\).
Recall from Calculus that the Taylor series expansion of \(e^x\) is given by
\(e^x = \displaystyle \sum_{k=0}^{\infty} \dfrac{x^k}{k!}\),
and thus the result then follows by substituting \(x=-1\).
Usually we're not as interested in \(d_n\) itself as we are in enumerating permutations with certain restrictions, as the following example illustrates.
Consider the Hat Check problem, but suppose instead of wanting no man to leave with his own hat, we are interested in the number of ways to distribute the 100 hats so that precisely 40 of the men leave with their own hats.
If 40 men leave with their own hats, then there are 60 men who do not receive their own hats. There are \(C(100,60)\) ways to choose the 60 men who will not receive their own hats and \(d_{60}\) ways to distribute those hats so that no man receives his own. There's only one way to distribute the 40 hats to the men who must receive their own hats, meaning that there are
\(\dbinom{100}{60}d_{60} = 42078873492228172128327462833391345210773815159514072218289944467852500232068048628965153767728913178940196920\)
such ways to return the hats.