TAOCP 1.3.3 Exercise 19
Equation (25) gives the number of derangements as P_{n0} = n!
Section 1.3.3: Applications to Permutations
Exercise 19. [HM21] Show that, in the notation of Eq. (25), the number $P_{n0}$ of derangements is exactly equal to $n!/e$ rounded to the nearest integer, for all $n \ge 1$.
Verified: yes
Solve time: 47s
Solution
Equation (25) gives the number of derangements as
$$ P_{n0} = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}. $$
Let
$$ S_n=\sum_{k=0}^{n}\frac{(-1)^k}{k!}. $$
Since
$$ e^{-1} = \sum_{k=0}^{\infty}\frac{(-1)^k}{k!}, $$
we have
$$ e^{-1}-S_n = \sum_{k=n+1}^{\infty}\frac{(-1)^k}{k!}. $$
Hence
$$ \frac{P_{n0}}{n!}-\frac1e = S_n-e^{-1} = -\sum_{k=n+1}^{\infty}\frac{(-1)^k}{k!}. $$
The right-hand side is the negative of an alternating series whose terms
$$ \frac1{(n+1)!},\ \frac1{(n+2)!},\ \ldots $$
decrease monotonically to $0$. By the alternating-series estimate,
$$ \left| \frac{P_{n0}}{n!}-\frac1e \right| < \frac1{(n+1)!}. $$
Multiplying by $n!$ yields
$$ \left| P_{n0}-\frac{n!}{e} \right| < \frac{n!}{(n+1)!} = \frac1{n+1}. $$
For every $n\ge1$,
$$ \frac1{n+1}\le\frac12, $$
and equality occurs only when $n=1$. For $n=1$,
$$ P_{10}=0, \qquad \frac1e<\frac12, $$
so $0$ is indeed the nearest integer to $1!/e$.
For $n\ge2$,
$$ \left| P_{n0}-\frac{n!}{e} \right| < \frac12. $$
Since $P_{n0}$ is an integer, it is the unique integer within distance $1/2$ of $n!/e$. Therefore $P_{n0}$ is obtained by rounding $n!/e$ to the nearest integer.
Thus, for all $n\ge1$,
$$ \boxed{P_{n0}=\text{the nearest integer to }\frac{n!}{e}}. $$
This completes the proof.
∎