# 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)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)Substituting $x = -1$ gives us:

(3)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)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)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)The true number of derangements $D_6$ is $265$.