Multiplicar por un número irracional en problemas de combinatoria

Question

Todo el mundo sabe que el número de alteraciones de un conjunto de tamaño $n$ es el entero más cercano a $n!/e$.

También es ampliamente conocido que el $(n+1)$ésimo número de Fibonacci $F_{n+1}$ es el entero más cercano a $(1+\sqrt{5})F_n/2$ donde $F_n$ $n$ésimo número de Fibonacci (con la única excepción de que $F_2=F_1$).

Había escapado a mi atención hasta el día de hoy, cuando escribí esta respuesta, que el número de secuencias de los distintos elementos de un conjunto de tamaño $n$ (incluyendo los de longitud de $0$) es el entero más cercano a $n!e$. (Nota posterior: Proporcionado $n\ge2$.)

¿Qué tan extendida está esta operación de mulitplying por un número irracional y, a continuación, redondeo, en problemas de combinatoria? Hay otros ejemplos? Hay una teoría general de la contabilidad para esto?

Postscript algunas horas más tarde: Si no me equivoco, la secuencia cuyas $n$th término es el entero más cercano a $n!e$ satifies la recurrencia $x_{n+1} = (n+1)x_n + 1$.

Answer 1

El número de rutas de acceso desde el vértice $v_1$ $v_2$en un grafo completo en $n$ vértices es $$\sum_{k=0}^{n-2}\dfrac{(n-2)!}{k!}=\lfloor(n-2)!e\rfloor$$

Para ver por qué se nota que $e=1+1+\frac{1}{2}+\frac1{3!}+\cdots+\frac{1}{(n-1!)}+\cdots$

Por lo $\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$

Pero la suma al final es menos de $1$$n\geq3$. (para ver por qué, ver que la suma al final es estrictamente menor que el geometrc serie $(n-1)+(n-1)^2+(n-1)^3+\cdots$ que es exactamente $1$ al$n$$3$.