Derangements

Now let's consider a situation where we can make use of the properties defined in . 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,\dots,n\). For example, the permutation \(\sigma\) given below is a derangement, while \(\tau\) 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,\dots,n\).

As before, the principal result of this section follows immediately from the lemma and the .

For example, \[\begin{aligned}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{aligned}\]

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.

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.