# The Number of Derangements

$$\displaystyle \lim_{n\to\infty} \frac {!n}{n!} = \frac {1}{e} \approx 0.3679…$$

Read as : the limit, as $$n$$ approaches infinity, of subfactorial $$n$$ divided by factorial $$n$$ is equal to $$1$$ divided by $$e$$ which approximates to $$0.3679$$, where $$e$$ is Euler’s number, $$e = 2.71828…$$

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} \{1,2,3\}\\ \{1,3,2\}\\ \{2,1,3\}\\ \{2,3,1\}\\ \{3,1,2\}\\ \{3,2,1\} \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\}$$.  This because everything is out of place; there are 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.

When $$n = 4$$,

$$\displaystyle !4 \approx \frac{4!}{e} \approx \frac{24}{e} \approx 8.8291…$$

We can say :

$$\displaystyle !n = \left[\frac {n!}{e}\right]$$,

where [ ] is the nearest whole integer function.

The following recurrence relationships also 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})$$,

where $$D_n$$ is the $$nth$$ derangement.

When $$n = 4$$,

$$D_4 = 4D_3 + (-1)^4 = 4\cdot 2 + 1 = 9$$

and

$$D_4 = 3(D_3 + D_2) = 3(2 + 1) = 9$$

© OldTrout $$2020$$