Expresan una forma recursiva de la función definida en términos de factoriales o de la función gamma

Question

Dada la recursividad

$$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$

¿Cómo se hace exactamente expresar la función de destino?

---

Sé que

$$f(n) = nf(n-1)$$

da lugar a

$$f(n) = \Gamma(n+1)$$

En varias ocasiones sustituyendo I puede entonces deducir

$$f(n) = \Gamma(n+1) + (n-1)f(n-2) + n(n-2)f(n-3) + n(n-1)(n-3)f(n-4) ... $$

Dónde ir a partir de ahí?

Answer 1

Se puede considerar que las similares y bien conocido recursividad $!n=(n-1)[!(n-1)+!(n-2)]$ donde $!k$ denota el subfactorial de $k$. La secuencia empieza con $!1=0$$!2=1$, y continúa de acuerdo a la recursividad con $!3=2$, $!4=9$, y así sucesivamente. El subfactorial de $k$ expresa el número de permutaciones de $k$ objetos en los que no hay ningún objeto que aparece en su "lugar natural" (es decir, para los números enteros, la posición después de haber sido ordenado).

Llamar a $f(x)$ el recurrente fórmula que se describe en la pregunta, tenemos $f(1)=1$$f(2)=3$. Entonces podemos notar que $f(1)=\displaystyle \frac{!3}{2}$$f(2)=\displaystyle \frac{!4}{3}$.

Si ahora queremos calcular el $f(3)$, podemos escribir $$f(3)= 3\cdot f(2)+2\cdot f(1)= 3\cdot \displaystyle \frac{!4}{3} + 2 \cdot \displaystyle \frac{!3}{2}=!4\,+ \,!3$$

y observando que $!4\, + \,!3=\displaystyle \frac{!5}{4}$ tenemos

$$ f(3)=\displaystyle \frac{!5}{4}$$

Por lo tanto, las relaciones de $ f(1)=\displaystyle \frac{!3}{2}$ $ f(2)=\displaystyle \frac{!4}{3}$ continuar con $ f(3)=\displaystyle \frac{!5}{4}$. Repitiendo el proceso, se obtiene que $ f(4)=\displaystyle \frac{!6}{5}$, $ f(5)=\displaystyle \frac{!7}{6}$, y así sucesivamente. Generalizando, tenemos que

$$ f(n)=\displaystyle \frac{!(n+2)}{(n+1)}$$

Desde el subfactorial está vinculado a la función gamma incompleta por la relación $!k=\displaystyle \frac{\Gamma(k+1, -1)}{e}$, podemos concluir que

$$f(n)=\displaystyle \frac{\Gamma(n+3, -1)}{e\cdot(n+1)}$$

En consecuencia, la última fórmula de los rendimientos de $n=1,2,3,4,5....$ los valores de $1,3,11,53,309....$, que corresponden a los obtenidos por la recursividad se describe en la OP. También tenga en cuenta que la fórmula funciona para$n=0$, ya que los rendimientos de $1$.