AC Derangements

Section 7.4 Derangements

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]\text{.}\) A permutation \(\sigma\in X\) is called a derangement if \(\sigma(i)\neq i\) for all \(i=1,2,\dots,n\text{.}\) For example, the permutation \(\sigma\) given below is a derangement, while \(\tau\) is not.

\(i\)	1	2	3	4
\(\sigma(i)\)	2	4	1	3

\(i\)	1	2	3	4
\(\tau(i)\)	2	4	3	1

If we again let \(P_i\) be the property that \(\sigma(i)=i\text{,}\) then the derangements are precisely those permutations which do not satisfy \(P_i\) for any \(i=1,2,\dots,n\text{.}\)

Lemma 7.10.

For each subset \(S\subseteq [n]\text{,}\) \(N(S)\) depends only on \(|S|\text{.}\) In fact, if \(|S|=k\text{,}\) then

\begin{equation*} N(S) = (n-k)! \end{equation*}

Proof.

For each \(i\in S\text{,}\) 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.

Theorem 7.11.

For each positive integer \(n\text{,}\) the number \(d_n\) of derangements of \([n]\) satisfies

\begin{equation*} d_n=\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)!. \end{equation*}

For example,

\begin{align*} d_5 \amp =\binom{5}{0}5!-\binom{5}{1}4!+\binom{5}{2}3!-\binom{5}{3}2!+ \binom{5}{4}1!-\binom{5}{5}0!\\ \amp =120-120+60-20+5-1\\ \amp =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\text{,}\) as the following result shows.

Theorem 7.12.

For a positive integer \(n\text{,}\) let \(d_n\) denote the number of derangements of \([n]\text{.}\) Then

\begin{equation*} \lim_{n\rightarrow\infty}\frac{d_n}{n!} = \frac{1}{e}. \end{equation*}

Equivalently, the fraction of all permutations of \([n]\) that are derangements approaches \(1/e\) as \(n\) increases.

Proof.

It is easy to see that

\begin{align*} \frac{d_n}{n!} \amp = \frac{\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)!}{n!}\\ \amp = \sum_{k=0}^n (-1)^k \frac{n!}{k!(n-k)!}\frac{(n-k)!}{n!}\\ \amp = \sum_{k=0}^n (-1)^k \frac{1}{k!}. \end{align*}

Recall from Calculus that the Taylor series expansion of \(e^x\) is given by

\begin{equation*} e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}, \end{equation*}

and thus the result then follows by substituting \(x=-1\text{.}\)

Usually we're not as interested in \(d_n\) itself as we are in enumerating permutations with certain restrictions, as the following example illustrates.

Example 7.13.

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

\begin{align*} \binom{100}{60}d_{60} = \amp 420788734922281721283274628333913452107738151595140722182899444\\ \amp 67852500232068048628965153767728913178940196920 \end{align*}

such ways to return the hats.