Stirling number relation Let $S(k,n)$ denote the Stirling number, i.e. the number of ways to partition $k$ distinguishable objects into $n$ indistinguishable blocks. Then consider $S(n+r,n)$ for some fixed $r$, how can I show that $S(n+r,n)$ is a polynomial in $n$ of degree $2r$?

Here is a combinatorial approach. The $S(n+r,n)$ is the number of ways to partition set of size $n+r$ into $n$ non-empty subsets. We can count such possibilities by summing over different possible counts $k_1,k_2,\dots,k_n$ such that $k_1+k_2+\dots+k_n=n+r$. Since each set is non-empty, we have at least one element in each (i.e. $k_i \geq 1$), however we can focus only on subsets that have more than $1$ element. Once we count these, rest of the subsets are uniquely determined (all singletons).
So assume we have $t$ subsets with more than $1$ element. We will also need to consider cases where some subsets have equal number of elements (since the order does not matter). So, we have distinct sizes $m_1,m_2,\dots,m_s$ where each $m_i > 1$ occurs $n_i \geq 1$ times ($n_1+\dots+n_s=t$), and
$$n_1m_1+n_2m_2+\dots+n_sm_s=r+t.\tag{*}$$
To count number of partitions of these particular sizes, we simply select $m_1$ elements for repeatedly $n_1$ times from $n+r$ (and divide by $n_1!$ since order does not matter), then we select $m_2$ elements repeatedly from $n_2$ times from remaining $n+r-n_1m_1$ (again divide by $n_2!$), and so on, until we have only singleton subsets. Thus we get
$$
S(m_1,\dots,m_s;n_1,\dots,n_s)=\\
\binom{n+r}{m_1}\binom{n+r-m_1}{m_1}\cdots\binom{n+r-(n_1-1)m_1}{m_1}\frac{1}{n_1!}\\
\cdot \binom{n+r-n_1m_1}{m_2}\cdots\binom{n+r-n_1m_1-(n_2-1)m_2}{m_2}\frac{1}{n_2!}\\
\vdots\\
=\prod_{k=1}^{s}\frac{1}{n_k!}\prod_{j=0}^{n_k-1} \binom{n+r-\sum_{i=1}^{k-1}(n_im_i)-jm_k}{m_k}
$$
Total count of all partitions will be just sum over all possible sizes $m_i,n_i,t$:
$$
S(n+r,n)=\sum_{\substack{n_1+\dots+n_s=t \\ n_1m_1+n_2m_2+\dots+n_sm_s=r+t \\m_i > 1, n_i \geq 1, r \geq t \geq 1}} S(m_1,\dots,m_s;n_1,\dots,n_s) \tag{**}
$$
Notice that $\binom{n-a}{b}=\frac{1}{b!}(n-a)(n-a-1)\cdots(n-a-(b-1))$ for positive integer $b$ is a polynomial in $n$ of degree $b$. Since $(**)$ is sum of products of such binomials, it is also a polynomial in $n$. Furthermore, since each term has positive leading coefficient, we can evaluate its degree by looking at the maximal degree of individual terms, each such degree is given by $(*)$. Note also that $t \leq r$ (if we had more than $r$ subsets with more than one element, we would have to start with more than $2r+(n-r)=n+r$ elements, impossible). Finally, the maximum is achieved by $s=1$, $m_1=2$, $n_1=r$, and thus the maximal degree of a term is $n_1m_1=2r$, and so is the degree of $S(n+r,n)$.
Example. Let's illustrate the idea on $r=3$. Since $3=1+2=1+1+1$, we can consider three cases for the sizes of subsets with more than one element being $[4]$, $[2,3]$ and $[2,2,2]$ respectively. In terms of the above notation (where we work with distinct sizes and multiplicities instead), we have:
First, $t=1,n_1=1,m_1=4$, and we get $\frac{1}{1!}\binom{n+3}{4}$ (degree is $3+t=4$).
Second, $t=2,n_1=1,m_1=2,n_2=1,m_2=3$, we get $\frac{1}{1!}\binom{n+3}{2}\frac{1}{1!}\binom{n+1}{3}$ (degree is $3+t=5$).
Third (last), $t=3,n_1=3,m_1=2$, we get $\frac{1}{3!}\binom{n+3}{2}\binom{n+1}{2}\binom{n-1}{2}$ (degree is $3+t=6$, the maximal).
Thus, $$S(n+3,n)=\binom{n+3}{4}+\binom{n+3}{2}\binom{n+1}{3}+\frac{1}{6}\binom{n+3}{2}\binom{n+1}{2}\binom{n-1}{2}.$$
Note. It's not hard to see that we could also simplify the product in the sum above into
$$
S(m_1,\dots,m_s;n_1,\dots,n_s)=(n+r)_{r+t}\cdot \prod_{k=1}^{s} \frac{1}{n_k! (m_k!)^{n_k}}
$$
where $(x)_n=x(x-1)\cdots (x-n+1)$ is the falling factorial.
We can also write this as a formula for $S(a,b)$ with $a>b$:
$$
S(a,b)=\sum_{\substack{n_1+\dots+n_s=t \\ n_1m_1+n_2m_2+\dots+n_sm_s=a-b+t \\m_i > 1, n_i \geq 1, a-b \geq t \geq 1}} (a)_{a-b+t}\cdot\prod_{k=1}^{s} \frac{1}{n_k! (m_k!)^{n_k}}
$$
(technically works also with $a<b$ as the sum will be empty and so zero).
Or after pulling out common part in falling factorial we may write:
$$
\bbox[#ffd,10px]{S(a,b)=(a)_{a-b}\sum_{t=1}^{a-b}(b)_t\sum_{\substack{n_1+\dots+n_s=t \\ n_1m_1+\dots+n_sm_s=a-b+t \\m_i > 1, n_i \geq 1}}\prod_{k=1}^{s} \frac{1}{n_k! (m_k!)^{n_k}}}.\tag{***}
$$
Here we can again see that for constant $a-b$ the most inner sum will be just some rational number, and also $(a)_{a-b}$ will be a polynomial in $a$ of constant degree $a-b$. I include this version here since it also slightly simplifies the inner sum (but it is still essentially enumeration of some partitions). Also don't forget that $m_i$ are distinct integers, we might write $m_1<m_2<\dots < m_s$, which also takes care of order.
