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. 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\%$$. 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!}$$