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?

Improve this question
$\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$
    – Gerhard Paseman
    Commented Dec 12, 2017 at 1:10
  • $\begingroup$ @GerhardPaseman You puzzle me strangely... $\endgroup$
    – Igor Rivin
    Commented 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$
    – Gerhard Paseman
    Commented 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
    Commented Dec 12, 2017 at 1:53
  • 1
    $\begingroup$ See also 2.2 Examples and Special Cases in Enumerative Combinatorics (p. 227). $\endgroup$
    – Benjamin Dickman
    Commented Dec 12, 2017 at 3:26

1 Answer 1

Reset to default
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)$$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .