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!
 A: 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$.
A: 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.
