Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
5  
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
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.