# The proportion between permutations and derangements.

Denote the number of derangements by $D_N$. It's known that $D_N/N! \rightarrow 1/e$. Therefore $N!/e$ is an approximation for $D_N$.

I'm trying to bound the difference between this approximation and $D_N$. Namely, to bound from above $|N!/e - D_N|$ as a function of $N$.

I believe it will help me to know from which value of $N_0$, it holds that for every $N > N_0$: $|N!/e - D_N| < 2^{-k}$ for some $k$.

Any help will be appreciated!

-
You can get an exact figure from inclusion-exclusion. The difference is between $1/(N+1)$ and $1/(N+2)$. See en.wikipedia.org/wiki/Derangement – S. Carnahan Jun 16 '13 at 13:12

I might as well turn my comment into an answer. From the Taylor expansion of the exponential function applied to $e^{-1}$, we have: $$\frac{N!}{e} = \left( \sum_{k=0}^N (-1)^k \frac{N!}{k!} \right) + \left( \sum_{j=N+1}^\infty (-1)^j \frac{N!}{j!} \right)$$ where the first sum is an integer, and the second sum has absolute value between $\frac{1}{N+2}$ and $\frac{1}{N+1}$.
From the Wikipedia article on derangements, we see that the first sum is in fact equal to the number of derangements. This can be deduced by an inclusion-exclusion argument. Your error term $\left| \frac{N!}{e} - D_N \right|$ is therefore between $\frac{1}{N+2}$ and $\frac{1}{N+1}$. For your last question, if you want $\left| \frac{N!}{e} - D_N \right| < 2^{-k}$ for all $N\gt N_0$, it is necessary and sufficient that $N_0 > 2^k-2$.
There is a convergent series \begin{equation*} D_N -\frac{N!}{e}=\frac{(-1)^N}{e}\sum_{k=0}^\infty \frac{1}{(k+N+1)k!} \end{equation*} from which we get the asymptotic series $$D_N -\frac{N!}{e}\approx(-1)^N \left(\frac{1}N -\frac{2}{N^2}+\frac{5}{N^3} -\frac{15}{N^4}+\cdots\right)$$ where the coefficients are Bell numbers.