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.

Sil
  • 16,612
Jostein Trondal
  • 378

2 Answers2

2

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.

Brian M. Scott
  • 616,228
Jostein Trondal
  • 378
  • 1
    This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review – user37238 Apr 01 '16 at 13:33
  • 1
    @user37238: The OP is reporting an answer they discovered, with a fairly clear indication of sources. While other Answers may supply more detail, I think this is a valuable post that should not be deleted. – hardmath Apr 01 '16 at 13:43
  • Thank you for improving the typography, Professor Scott! – Jostein Trondal Apr 04 '16 at 07:11
1

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)!$

Mastrem
  • 8,331