The Number of Derangements

\(\displaystyle \lim_{n\to\infty} \frac {!n}{n!} = \frac {1}{e}\)

 

The Hat Check Problem, as first described by Montmort in \(1713\), considers the following problem :

A group of \(n\) people enter a restaurant and check their hats.  On leaving,
the hat-checker gives the hats back in a random order.  What is the
probability that no one gets the correct hat?

In combinatorics, a derangement is a permutation in which none of the objects appear in their ordered place; that is, they have no fixed points.

The number of derangements of \(n\) is called the subfactorial of \(n\) and is denoted by \(!n\).  The number of permutations is \(n\) factorial denoted by \(n!\).

The permutations of the ordered set \(\{1, 2, 3\}\) are :

\(\begin{array}{c c c}
123\\
132\\
213\\
231\\
312\\
321
\end {array} \)

There are a total of \(3! = 1\times2\times3 = 6\) permutations.  Of these, two are derangements, namely \(2\;3\;1\) and \(3\;1\;2\).  They have no fixed points.

OldTrout, Going Postal

Thus, the probability of derangement is \(2/6 = 1/3 = 33\%\).

When \(n = 4\), \(!n = 9\) and \(n! = 24\) and the probability is \(9/24 = 3/8 = 37.5\%\).

OldTrout, Going Postal

The numbers grow very quickly and the limit of \(1/e\) is rapidly approached.

\(
\begin{array}{c| c c c c}
n & !n &n! &!n/n! & \%\\
\hline
1&0&1&0&0\\
2&1&2&1/2&50\\
3&2&6&1/3&33.33\\
4&9&24&3/8&37.50\\
5&44&120&11/30&36.67\\
6&265&720&53/144&36.81\\
7&1854&5040&103/280&36.79
\end{array}
\)

 

By rearranging the above equation, we have the approximation :

\(\displaystyle !n \approx \frac {n!}{e}\)

By rounding to the nearest whole number, the value of \(!n\) is found.

The following recurrence relationships hold :

\(!n = D_n\) with \(D_1 = 0\) and \(D_2 = 1\)

\(D_n = nD_{n-1} + (-1)^n\)

and

\(D_n = (n-1) (D_{n-1} + D_{n-2})\)

 

Using the Inclusion-Exclusion principle,  we find the following sum :

\(\displaystyle !n = n!\left(1\, – \frac{1}{1!} + \frac{1}{2!}\, – \frac{1}{3!} + \frac{1}{4!} . . . \pm \frac{1}{n!}\right) = n!\sum_{k = 0}^n \frac{(-1)^k}{k!}\)

 

© OldTrout 2018