10
$\begingroup$

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

  • 0
    Have you tried entering first few terms in OEIS?..2011-11-15
  • 0
    Grigory - this is a good idea, and yes - I've tried it but nothing came up.2011-11-15
  • 0
    The exponential generating function reminds me of that of the Bernoulli numbers (http://mathworld.wolfram.com/BernoulliNumber.html), but I don't know how to make the connection useful.2011-11-15
  • 0
    This same sequence also appeared in project Euler [problem 330](http://projecteuler.net/problem=330).2011-11-17
  • 0
    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.2011-11-19

3 Answers 3

10

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

  • 0
    Thank you. Also, I added now the initial condition (A_0=1).2011-11-15
  • 1
    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.2011-11-15
8

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.

  • 0
    This seems like a downgrade in complexity from $O(n^2)$.2011-11-15
  • 0
    At least it's not a recurrence, though, so +1.2011-11-15
  • 0
    @Mike, thanks. See edit.2011-11-15
  • 0
    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.2011-11-15
  • 3
    The numbers in your inner sum are apparently called the "Fubini numbers" or "ordered Bell numbers." There's an interesting discussion of them [here](http://books.google.com/books?id=5iK9OX9z014C&pg=PA396&lpg=PA396&dq=fubini+numbers&source=bl&ots=08cbcTU21B&sig=-pfarb8jfVNybI0vbNfiBzaY6Gc&hl=en&ei=gLPCToDPCpLSiAKFvfH_Cw&sa=X&oi=book_result&ct=result&resnum=3&ved=0CDMQ6AEwAg#v=onepage&q=fubini%20numbers&f=false). They're also the numbers Brian mentions in his answer as OEIS A000670.2011-11-15
  • 0
    Applying the approximation in the previous reference, one gets $A_n/n! \approx c^{n+1}/(2c-2)$ where $c=1/log(2)$. Works quite well.2011-11-15
4

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.

  • 0
    By Stirling's approximation, computation of $n!$ must take $\Omega(n\lg{n})$, right?2011-11-15
  • 0
    @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).2011-11-15
  • 0
    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!$.2011-11-15
  • 0
    Thank you. I also recommend Analytic Combinatorics, but I "need" the exact numbers and not an estimate in this case.2011-11-15