Resolver la relación de recurrencia $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$

Question

Estoy tratando de resolver la relación de recurrencia $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$ con la condición inicial $A_0=1$. Por "resolver" me refiero a encontrar una manera eficaz de computación $A_n$ general $n$ en la complejidad de la mejor de $O(n^2)$.

He intentado utilizar la identidad de $\dbinom{n+1}i=\dbinom{n}{i-1}+\dbinom{n}i$ pero aún así terminó con una suma de todos los anteriores $n$'s.

Otro enfoque fue el aviso de que $2A_n=n!+\sum_{i=0}^{n}{n \choose i}A_{n-i}$ si $a(x)$ es la EFG para $A_n$, entonces obtenemos la relación $$2a(x)=\frac{1}{1-x}+a(x)e^x,$$ so $$a(x)=\frac{1}{(1-x)(2-e^x)}$$ (am I correct here?) but I can't see to to use this EGF for the more efficient computation of $A_n$.

Answer 1

Esta no es una respuesta, pero puede llevar a referencias útiles.

La forma de la recurrnce sugiere dividir por $n!$ y la sustitución de $B_n=\dfrac{A_n}{n!}$, después de que la repetición se convierte en $$B_n=1 + \sum_{i=1}^n\binom{n}i\frac{(n-i)!}{n!}B_{n-i}=1+\sum_{i=1}^n\frac{B_{n-i}}{i!}.$$

Usted no especifica una condición inicial, por lo que para el primer par de términos, tenemos: $$\begin{align*} B_0&=0+B_0\\ B_1&=1+B_0\\ B_2&=2+\frac32B_0\\ B_3&=\frac72+\frac{13}6B_0\\ B_4&=\frac{17}3+\frac{25}8B_0\\ B_5&=\frac{211}{24}+\frac{541}{120}B_0 \end{align*}$$

Si establecemos $B_n=u_n+v_nB_0$, luego $$u_n=1+\sum_{i=1}^n\frac{u_{n-i}}{i!}$$ with $u_0=0$, and $$v_n=\sum_{i=1}^n\frac{v_{n-i}}{i!}$$ with $v_0=1$. The ‘natural' denominator of $u_n$ is $(n-1)!$, while that of $v_n$ is $n!$, so I looked at the sequences $$\langle (n-1)!u_n:n\in\mathbb{N}\rangle = \langle 0,1,2,7,34,211,\dots\rangle$$ and $$\langle n!v_n:n\in\mathbb{N}\rangle=\langle 1,1,3,13,75,541,\dots\rangle\;.$$ La primera es OEIS A111539, y la segunda parece ser OEIS A000670. Hay, evidentemente, una gran cantidad conocida sobre esto último, hay muy poco de lo primero.

Añadió: Y con $A_0=1$ tenemos $B_0=1$$B_n=u_n+v_n$.

Answer 2

Usted puede, sin duda, al menos, la estimación de $\frac{A_n}{n!}$ con bastante precisión y el uso eficiente del EGF por la suma de las contribuciones de los coeficientes más de lo suficiente de los polos de la función de la generación de $a(z) = \frac{1}{(1 - z)(2 - e^z)}$. Hay polos en $z = 1, \log 2 + 2 \pi i k, k \in \mathbb{Z}$; calcular los residuos en estos polos y se obtiene una expresión para $\frac{A_n}{n!}$ como una suma de términos de la forma $c_{\lambda} \lambda^n$ donde $\lambda$ ejecuta a través de los recíprocos de los polos. El $\lambda$ disminuir rápidamente. Para más detalles véase, por ejemplo, Flajolet y Sedgewick de la Analítica de la Combinatoria.

Estoy medianamente curioso lo que necesita un valor exacto de $A_n$. Si usted sabe cómo calcular $n!$ eficiente (y yo no) usted puede utilizar la cantidad suficiente de términos en la anterior suma que su error es mejor que el de $\frac{1}{n!}$, que no llevará demasiado tiempo.

Answer 3

Desde $(1-x)^{-1}=\sum\limits_{i=0}^{+\infty}x^i$$(2-\mathrm e^x)^{-1}=\sum\limits_{j=0}^{+\infty}2^{-j-1}\mathrm e^{jx}$, el número de $A_n/n!$ $x^n$ plazo en $$ \sum\limits_{i=0}^{+\infty}x^i\cdot\sum\limits_{j=0}^{+\infty}2^{-j-1}e^{jx}=\sum\limits_{i=0}^{+\infty}x^i\cdot\sum\limits_{j=0}^{+\infty}2^{-j-1}\sum\limits_{k=0}^{+\infty}\frac{j^k}{k!}x^k, $$ que es $$ A_n=n!\cdot\sum\limits_{j=0}^{+\infty}2^{j-1}\sum\limits_{k=0}^{n}\frac{j^k}{k!}. $$ Ahora, el uso de dos hechos. En primer lugar, para cada $j$$k$, $$ j^k=\sum\limits_{i=0}^{k}\left\{{k\cima i}\right\}\cdot(j)_i, $$ donde $\left\{{k\atop i}\right\}$ son números de Stirling del segundo tipo y $(j)_i$ es un símbolo de Pochhammer. Segundo, el uso por el valor de $z=\frac12$ el hecho general de que, para cada $|z|\lt1$, $$ \sum\limits_{j=0}^{+\infty}(j)_i\cdot z^{j+1}=\frac{i!\cdot z^{i+1}}{(1-z)^{i+1}}. $$ Esto produce que, finalmente, $A_n$ como finito doble de la suma, es decir, $$ \color{red}{A_n=n!\cdot\sum\limits_{k=0}^{n}\frac1{k!}\sum\limits_{i=0}^{k}i!\cdot\left\{{k\cima i}\right\}=n!\cdot\left(1+\sum\limits_{k=1}^{n}\frac1{k!}\sum\limits_{i=1}^{k}i!\cdot\left\{{k\cima i}\right\}\right)}. $$ Nota: Uno me dice los números en el interior de las sumas que se llaman Fubini números o ordenado de la Campana de los números.