# Any ideas for an explicit formula?

1. Mar 21, 2013

### Someone2841

Let an,m be defined for the non-negative integers n and m such that n ≥ m.

an,0 = 1
am,m = m!
an+1,m+1 = (m+1) * an,m + an,m+1

Is there an explicit formula f such that f(n,m) = an,m?

Here are the first numbers of the sequence:

\begin{align} &m&0&1&2&3&4\\ n\\ 0&&1\\ 1&&1&1\\ 2&&1&3&2\\ 3&&1&6&11&6\\ 4&&1&10&35&50&24\\ 5&&1&5&85&225&274&12\\ \end{align}

2. Mar 21, 2013

### conquest

Hi!

So first of all I wouldn't recommend choosing the title you chose it doesn't say anything about the problem so people that actually know the answer might just skip it.

Also it seems that your third formula gives me an expression for $a_{n,m}$ with n smaller then m if you fill in $a_{m+1,m+1}$. So either you need to state explicitely that that formula only goes for n strictly greater than m or since the outcome is just that these $a_{n,m}$ with n smaller than m are 0 just define them to be 0. This also takes away the need for the second identity since in the case you put these to 0 it is implied by the third!

So doing it this way I just start with the first identity and fill in the recursive relation again. which yields (so here $n\geq m\geq 1$)
$a_{n,m}=ma_{n-1,m-1}+a_{n-1,m}=m(m-1)a_{n-2,m-2} +a_{n-1,m} +ma_{n-2,m-1}=\ldots=m!a_{n-m,0}+\displaystyle\sum_{i=1}^m \frac{m!}{(m+1-i)!}a_{n-i,m+1-i}\\=m!(1+\displaystyle\sum_{i=1}^m \frac{a_{n-i,m+1-i}}{(m+1-i)!})$.

So now we just have to figure out that sum. Which I think is quite doable, I did it a little bit, but it will probably cost some time to do it this way. SO maybe someone else has a shorter way. If not this will definitely work if you just keep putting the recurrence relation in until you know that you are just adding zeros or ones and then you are done. For instance as a next step the sum will split into another sum and a shorter sum. Doing this will give you a double sum with all indices reduced and something lke (n-m+1) or something like that. Then you keep on making every sum shorter and getting shorter double sums or tripple sums or whatever and eventually you will just get some kind of m tuple sum that only has 1 term anyway and then you are done. This may not be the most elegant way to solve the problem, but at least it works.