Two dimensional recurrence relation $f(n,k)=f(n-1,k)\cdot(n-1) + f(n-1,k-1)$ I'm struggling to get the following recurrence relation into a closed form if possible:
$$f(n,n)=1$$
$$f(n,1)=(n-1)!$$
$$f(n,k)=f(n-1,k)\cdot(n-1) + f(n-1,k-1)$$
where $f$, $n$ and $k$ are positive integers, and $k\leq n$. I've tried to plug the formulas to look for patterns, but I'm not doing very well... And, is there any software that can handle this kind of problem?
Edit: Removed redundant part of definition.
 A: Thank you, Mastrem, for valuable input.
It turns out that $f(n,k)={n\brack k}$, in other words (unsigned) Stirling numbers of the first kind.
I found this by searching the OEIS.
Edit: Fixed typo (from "signed" to "unsigned"), added the following:
Proof: From the Wikipedia-article Stirling numbers of the first kind we have a recurrence relation for these numbers:
$${{n+1}\brack k}=n{n\brack k}+{n\brack{k-1}}$$
With the substitution $n\rightarrow n-1$ we get
$${n\brack k}=(n-1){{n-1}\brack k}+{{n-1}\brack{k-1}}$$
which is exactly in the same form as
$$f(n,k)=f(n-1,k)\cdot(n-1)+f(n-1,k-1)$$
Looking at starting-values we also see that the initial conditions must be equivalent.
A: Say $k=n-1$. According to the third part of your definition:
$$f(n,n-1)=f(n-1,n-1)\cdot (n-1) + f(n-1,n-2)=f(n-1,n-2)+n-1$$
Let $A_n$ be $f(n, n-1)$. Now we have:
$$A_n = A_{n-1}+n-1$$
We have $A_2=1$ and thus:
$$A_n = \dfrac{(n-2)^2+n-2}{2}-n+4$$
So:
$$f(n,n-1)=\dfrac{(n-2)^2+n-2}{2}-n+4$$
Say $k=n-2$. Now:
$$f(n,n-2)=f(n-1,n-2)\cdot (n-1) + f(n-1, k-3)$$
using our definition of $A_n$:
$$f(n,n-2)=A_{n-1}(n-1)+f(n-1, n-3)=\bigg(\dfrac{(n-2)^2+n-2}{2}-n+4\bigg)(n-1)+f(n-1,n-3)$$
Now define $B_n = f(n,n-2)$:
$$B_n=\bigg(\dfrac{(n-2)^2+n-2}{2}-n+4\bigg)(n-1)+B_{n-1}$$
When you want to find $f(a,b)$, simply find the formula belonging to $f(n,n-(a-b))$ and use the fact that $f(n,1)=(n-1)!$
