Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$.

It is also widely known that the $(n+1)$th Fibonacci number $F_{n+1}$ is the nearest integer to $(1+\sqrt{5})F_n/2$ where $F_n$ is the $n$th Fibonacci number (with the lone exception that $F_2=F_1$).

It had escaped my attention until today, when I wrote this answer, that the number of sequences of distinct elements of a set of size $n$ (including those of length $0$) is the nearest integer to $n!e$. (Later note: Provided $n\ge2$.)

How widespread is this operation of mulitplying by an irrational number and then rounding, in combinatorial problems? Are there other standard examples? Is there some general theory accounting for this?

Postscript some hours later: If I'm not mistaken, the sequence whose $n$th term is the nearest integer to $n!e$ satifies the recurrence $x_{n+1} = (n+1)x_n + 1$.

  • 4
    $\begingroup$ The Fibonacci number thing works for any recurrence sequence for which the characteristic polynomial has one root greater than 1 (in modulus), the other roots being less than 1 (in modulus). See PV-numbers. $\endgroup$ – Gerry Myerson Sep 7 '13 at 23:53
  • $\begingroup$ Concerning the postscript, if $a_n=n!e$, then $a_{n+1}=(n+1)a_n$, trivially. Did you mean "nearest integer to $n!e$? $\endgroup$ – Gerry Myerson Sep 8 '13 at 4:22
  • $\begingroup$ fixed ${{{{{}}}}}$ $\endgroup$ – Michael Hardy Sep 8 '13 at 4:50
  • $\begingroup$ I've just posted a version of this question to mathoverflow: mathoverflow.net/questions/142446/… $\endgroup$ – Michael Hardy Sep 17 '13 at 23:25

The number of paths from vertex $v_1$ to $v_2$ in a complete graph on $n$ vertices is $$\sum_{k=0}^{n-2}\dfrac{(n-2)!}{k!}=\lfloor(n-2)!e\rfloor$$

To see why note that $e=1+1+\frac{1}{2}+\frac1{3!}+\cdots+\frac{1}{(n-1!)}+\cdots$

So $\displaystyle e(n-2)!=\left(\sum_{k=0}^{n-2}\dfrac{(n-2)!}{k!}\right)+\frac{(n-2)!}{n-1!}+\frac{(n-2)!}{n!}+\cdots$

But the sum at the end is less than $1$ for $n\geq3$. (to see why see that the sum at the end is strictly less than the geometrc series $(n-1)+(n-1)^2+(n-1)^3+\cdots$ which is exactly $1$ when $n$ is $3$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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