Solving the recurrence relation $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$ I am attempting to solve the recurrence relation $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$ with the initial condition $A_0=1$. By "solving" I mean finding an efficient way of computing $A_n$ for general $n$ in complexity better than $O(n^2)$.
I tried using the identity $\dbinom{n+1}i=\dbinom{n}{i-1}+\dbinom{n}i$ but I still ended up with a sum over all previous $n$'s.
Another approach was to notice that $2A_n=n!+\sum_{i=0}^{n}{n \choose i}A_{n-i}$ and so if $a(x)$ is the EFG for $A_n$, then we get the relation $$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$.

This isn’t an answer, but it may lead to useful references.
The form of the recurrnce suggests dividing through by $n!$ and substituting $B_n=\dfrac{A_n}{n!}$, after which the recurrence becomes $$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!}.$$
You didn’t specify an initial condition, so for the first few terms we have: 
$$\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*}$$
If we set $B_n=u_n+v_nB_0$, then $$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\;.$$ The first is OEIS A111539, and second appears to be OEIS A000670. There’s evidently a great deal known about the latter; there’s very little on the former.
Added: And with $A_0=1$ we have $B_0=1$ and $B_n=u_n+v_n$.
