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$