2
$\begingroup$

At some point the following question came up:

Is the number of derangements $D(n)$ the closest integer to $\frac{n!}e?$

Since $$D(n) = n! \sum_{i=0}^n \frac{(-1)^i}{i!},$$ the answer is YES by using the Lagrange form of the remainder in Taylor's theorem: $$\left|e^{-1} - \frac{D(n)}{n!}\right| = \frac{\exp{c_n}}{(n+1)!},$$ for some $c_n \in (-1, 0).$

Never content to leave well enough alone, we ask: how does $c_n$ depend on $n?$ Here are the experimental results, computed with Mathematica to $1000$ decimal places: the graph is of $1/c_n:$

Lagrange constant

It seems that, to high precision, $c_n \sim -1/n.$ Is this known? How would you prove such a thing?

$\endgroup$
7
  • $\begingroup$ Linear approximation of the exponential near zero? After all, exp c_n is pretty close to 1. Gerhard "That's What Your Graph Says" Paseman, 2017.12.11. $\endgroup$ Dec 12, 2017 at 1:10
  • $\begingroup$ @GerhardPaseman You puzzle me strangely... $\endgroup$
    – Igor Rivin
    Dec 12, 2017 at 1:23
  • $\begingroup$ Maybe I made an error. The quantity represented by exp c_n looks near 1 - 1/n to me. I am unsure about what prompts your question. It looks like an undergraduate exercise to me, but then I haven't put pencil to paper for this one yet . Gerhard "Others' Puzzlement Is Personally Puzzling" Paseman, 2017.12.11 $\endgroup$ Dec 12, 2017 at 1:39
  • $\begingroup$ @GerhardPaseman What prompted my question: curiosity. Undergraduate exercise: knock yourself out - it is not at all obvious (to my primitive high-school mind) that $c_n$ should even go to $0\dots$ $\endgroup$
    – Igor Rivin
    Dec 12, 2017 at 1:53
  • 1
    $\begingroup$ See also 2.2 Examples and Special Cases in Enumerative Combinatorics (p. 227). $\endgroup$ Dec 12, 2017 at 3:26

1 Answer 1

5
$\begingroup$

If I understand correctly,

$$\eqalign{\exp(c_n) &=(n+1)! \sum_{i=n+1}^\infty \frac{(-1)^{i-n-1}}{i!}\cr &= 1 - \frac{1}{n+2} + O(1/n^2)} $$ so indeed $$ c_n = \log \left(1 - \frac{1}{n+2} + O(1/n^2)\right) = -\frac{1}{n} + O(1/n^2)$$

$\endgroup$
2
  • $\begingroup$ Oh Robert, you make everything look like high school! Gerhard "Was Going For College-Level Answer" Paseman, 2017.12.11. $\endgroup$ Dec 12, 2017 at 3:16
  • $\begingroup$ Truly you are wise in the ways of science :) $\endgroup$
    – Igor Rivin
    Dec 12, 2017 at 4:08

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.