Estimating the Number of Derangements of Elements from a Finite Set

Recall from the Derangements page that if $A = \{1, 2, ..., n \}$ is a finite $n$-element set then a permutation $(x_1, x_2, ..., x_n)$ is said to be a derangement of the elements of $A$ if $x_i \neq i$ for all $i \in \{ 1, 2, ..., n \}$.

We also derived the following formula for the number of derangements $D_n$ using the inclusion-exclusion principle:

(1)

\begin{align} \quad D_n = n! \cdot \sum_{i=0}^{n} \frac{(-1)^i}{i!} = n! \left (1 - \frac{1}{1!} + \frac{1}{2!} + ... + \frac{(-1)^n}{n!} \right ) \end{align}

For $n$ decently sized, computing $D_n$ manually can we quite cumbersome. We will now derive an interesting estimate for $D_n$. First recall the Maclaurin series for $e^x$:

(2)

\begin{align} \quad e^x = \sum_{i=0}^{\infty} \frac{x^i}{i!} = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + ... \end{align}

Substituting $x = -1$ gives us:

(3)

\begin{align} \quad e^{-1} = \sum_{i=0}^{\infty} \frac{(-1)^i}{i!} = 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + ... \end{align}

Therefore $e^{-1}$ approximately equals the finite sum $\sum_{i=0}^{n} \frac{(-1)^i}{i!}$ with greater accuracy for large $n$, that is:

(4)

\begin{align} \quad e^{-1} \approx \sum_{i=0}^{n} \frac{(-1)^i}{i!} \end{align}

Substituting this into our formula for the number of deranges $D_n$ and we get an estimation for the number of derangements $D_n$:

(5)

\begin{align} \quad D_n \approx n! \cdot e^{-1} \\ \quad D_n \approx \frac{n!}{e} \end{align}

For example, suppose that we want to know the number of derangements of a $6$-element set $A = \{1, 2, 3, 4, 5, 6 \}$. Then from our approximation we have that:

(6)

\begin{align} \quad D_6 \approx \frac{6!}{e} = 264.8731 \approx 265 \end{align}

The true number of derangements $D_6$ is $265$.