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

-
Have you tried entering first few terms in OEIS?.. – Grigory M Nov 15 '11 at 10:45
Grigory - this is a good idea, and yes - I've tried it but nothing came up. – Gadi A Nov 15 '11 at 11:43
The exponential generating function reminds me of that of the Bernoulli numbers (mathworld.wolfram.com/BernoulliNumber.html), but I don't know how to make the connection useful. – Greg Martin Nov 15 '11 at 18:43
This same sequence also appeared in project Euler problem 330. – Sasha Nov 17 '11 at 21:16
Project Euler is indeed my motivation for checking it, but there might be a way around I'm missing to solve the PE problem, and I'm interested in the question of tackling this formula by its own right. – Gadi A Nov 19 '11 at 6:18

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

-
Thank you. Also, I added now the initial condition (A_0=1). – Gadi A Nov 15 '11 at 11:45
For $n=0$, $A_0=0!+\sum\limits_{i=1}^0\binom{0}{i}A_{0-i}$ says that $A_0=1$. It seems that this would be the initial condition. – robjohn Nov 15 '11 at 12:02

Since $(1-x)^{-1}=\sum\limits_{i=0}^{+\infty}x^i$ and $(2-\mathrm e^x)^{-1}=\sum\limits_{j=0}^{+\infty}2^{-j-1}\mathrm e^{jx}$, the number $A_n/n!$ is the $x^n$ term in $$\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,$$ that is $$A_n=n!\cdot\sum\limits_{j=0}^{+\infty}2^{-j-1}\sum\limits_{k=0}^{n}\frac{j^k}{k!}.$$ Now, use two facts. First, for every $j$ and $k$, $$j^k=\sum\limits_{i=0}^{k}\left\{{k\atop i}\right\}\cdot(j)_i,$$ where $\left\{{k\atop i}\right\}$ are Stirling's numbers of the second kind and $(j)_i$ is a Pochhammer symbol. Second, use for the value $z=\frac12$ the general fact that, for every $|z|\lt1$, $$\sum\limits_{j=0}^{+\infty}(j)_i\cdot z^{j+1}=\frac{i!\cdot z^{i+1}}{(1-z)^{i+1}}.$$ This yields finally $A_n$ as a finite double sum, namely, $$\color{red}{A_n=n!\cdot\sum\limits_{k=0}^{n}\frac1{k!}\sum\limits_{i=0}^{k}i!\cdot\left\{{k\atop i}\right\}=n!\cdot\left(1+\sum\limits_{k=1}^{n}\frac1{k!}\sum\limits_{i=1}^{k}i!\cdot\left\{{k\atop i}\right\}\right)}.$$ Note: One tells me the numbers in the inner sums are called Fubini numbers or ordered Bell numbers.

-
This seems like a downgrade in complexity from $O(n^2)$. – Zach Langley Nov 15 '11 at 14:24
At least it's not a recurrence, though, so +1. – Mike Spivey Nov 15 '11 at 16:44
@Mike, thanks. See edit. – Did Nov 15 '11 at 18:33
Even better. It's hard to see how to obtain a simpler (non-recursive) expression for $A_n$ than what you have at the end. – Mike Spivey Nov 15 '11 at 18:43
The numbers in your inner sum are apparently called the "Fubini numbers" or "ordered Bell numbers." There's an interesting discussion of them here. They're also the numbers Brian mentions in his answer as OEIS A000670. – Mike Spivey Nov 15 '11 at 18:50

You can certainly at least estimate $\frac{A_n}{n!}$ quite accurately and efficiently using the EGF by summing the contributions to the coefficients over enough of the poles of the generating function $a(z) = \frac{1}{(1 - z)(2 - e^z)}$. There are poles at $z = 1, \log 2 + 2 \pi i k, k \in \mathbb{Z}$; compute the residues at these poles and you get an expression for $\frac{A_n}{n!}$ as a sum of terms of the form $c_{\lambda} \lambda^n$ where $\lambda$ runs over the reciprocals of the poles. The $\lambda$ decrease rapidly. For more details see for example Flajolet and Sedgewick's Analytic Combinatorics.

I'm mildly curious what you need an exact value of $A_n$ for. If you know how to compute $n!$ efficiently (and I don't) you can use enough terms in the above sum that your error is better than $\frac{1}{n!}$, which shouldn't take too long.

-
By Stirling's approximation, computation of $n!$ must take $\Omega(n\lg{n})$, right? – Zach Langley Nov 15 '11 at 20:55
@Zach: exact computation? I don't know how easy it is to compute enough terms in the Stirling series (the first term is clearly not enough). – Qiaochu Yuan Nov 15 '11 at 20:58
I meant that the length of $n!$ is $\lg{n!}=\Theta(n\lg{n})$ by Stirling. Therefore, we need $\Omega(n\lg{n})$ time just to write down $n!$. – Zach Langley Nov 15 '11 at 21:09
Thank you. I also recommend Analytic Combinatorics, but I "need" the exact numbers and not an estimate in this case. – Gadi A Nov 15 '11 at 21:42