MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
You can get an exact figure from inclusion-exclusion. The difference is between $1/(N+1)$ and $1/(N+2)$. See – 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$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.