I'm having trouble understanding this exercise from Bóna's book "A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory"
It says:
Let m be a fixed positive integer. Prove that $S(n, n−m)$ is function of n. What is the degree of this polynomial?
He gives the answer and a short explanation; the proof is by induction on $m$ but I really don't understand why, and my second issue is about the result; he came to this:
$S(n,n-m)-S(n-1,n-m-1)=(n-m)S(n-1,n-1-(m-1))$
So he claims that the right-hand side is a polynomial by the inductive hypothesis, but I don't know where did this result come from.
Sorry if these are silly questions, I just can't get it, hope you can help me.
Best Answer
The formula is a rewritten form of the fundamental Stirling number of the second kind recurrence relation $$S(n, k) = S(n-1, k-1) + kS(n-1, k).$$
Maybe some extra notation would help. Let $f_m(n) = S(n, n-m)$. For each fixed $m$, you want to show $f_m(n)$ is a polynomial in $n$ of some to-be-determined degree. The rewritten recurrence relation is then $$f_m(n) - f_m(n-1) = (n-m)f_{m-1}(n-1).$$ By induction we're supposing $f_{m-1}$ on the right is a polynomial in $n$. Since $m$ is a constant, the whole product on the right is also a polynomial in $n$. It follows from the theory of finite differences (say) that $f_m$ itself is a polynomial in $n$. I'll let you think about the degree.