Multiplying by an irrational number in combinatorial problems

354 Views Asked by At

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