5
$\begingroup$

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!

$\endgroup$
1

2 Answers 2

16
$\begingroup$

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$.

$\endgroup$
12
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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