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$?
 A: Supposing  that ${n \brace k}$
is  the  Stirling number  of  the  second  kind  giving the  count  of
partitions of a set of $n$  distinguishable objects into $k$ non-empty subsets we seek to show that
$${n+r\brace n}$$
is a polynomial of degree $2r$ in $n.$ We start with the following
claim for $r\ge 0$:
$$\bbox[5px,border:2px solid #00A000]{
Q_r(z) = \sum_{n\ge 0} {n+r\brace n} z^n =
\frac{1}{(1-z)^{2r+1}}
\sum_{k=0}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
z^k.}$$
We will prove this by induction. Note that depending on whether
ball $n+r+1$ joins an existing set or becomes a singleton we have
$${n+r+1\brace n} = n {n+r\brace n} + {n+r\brace n-1}.$$
Multiply by $z^n$ and sum over $n\ge 0$ to get
$$Q_{r+1}(z) = z Q_r'(z) + \sum_{n\ge 1} {n+r\brace n-1} z^n
= z Q_r'(z) + z \sum_{n\ge 0} {n+r+1\brace n} z^n 
\\ = z Q_r'(z) + z Q_{r+1}(z).$$
This means we have
$$Q_{r+1}(z) = \frac{z}{1-z} Q_r'(z).$$
Now to prove the claim it certainly holds for $r=0$ by inspection.
It also holds for $r=1$ since
$$\sum_{n\ge 1} {n+1\choose 2} z^n 
= z \sum_{n\ge 1} {n+1\choose 2} z^{n-1}
= z \sum_{n\ge 0} {n+2\choose 2} z^n
= \frac{z}{(1-z)^3}.$$
For the induction step supposing it holds for $r\ge 1$ we differentiate
and multiply by $z/(1-z)$ to get for $Q_{r+1}(z)$
$$\frac{z}{1-z} \frac{2r+1}{(1-z)^{2r+2}}
\sum_{k=0}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
z^k
+ \frac{z}{1-z} \frac{1}{(1-z)^{2r+1}} 
\sum_{k=1}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
k z^{k-1}.$$
Factoring out $1/(1-z)^{2r+3}$ for the moment we are left with
$$(2r+1) \sum_{k=0}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
z^{k+1}
+ (1-z) \sum_{k=1}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
k z^k
\\ = (2r+1) \sum_{k=1}^{r+1}
\left\langle\!\! \left\langle r \atop k-1
\right\rangle\!\! \right\rangle
z^{k}
+ \sum_{k=0}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
k z^k
- \sum_{k=0}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
k z^{k+1}
\\ = (2r+1) \sum_{k=1}^{r+1}
\left\langle\!\! \left\langle r \atop k-1
\right\rangle\!\! \right\rangle
z^{k}
+ \sum_{k=0}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
k z^k
- \sum_{k=1}^{r+1}
\left\langle\!\! \left\langle r \atop k-1
\right\rangle\!\! \right\rangle
(k-1) z^{k}$$
Now with $r\ge 1$ we may extend the first and the third sum to include
$k=0$ and the second to include $k=r+1$ to obtain
$$\sum_{k=0}^{r+1} 
\left[ (2r+2-k) 
\left\langle\!\! \left\langle r \atop k-1
\right\rangle\!\! \right\rangle
+ k \left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle \right] z^k.$$
The  Eulerian  number recurrence  (second  order)  according to  OEIS
A349556 is
$$\left\langle\!\! \left\langle n \atop k
\right\rangle\!\! \right\rangle
=
k \left\langle\!\! \left\langle n-1 \atop k
\right\rangle\!\! \right\rangle
+ (2n-k) \left\langle\!\! \left\langle n-1 \atop k-1
\right\rangle\!\! \right\rangle$$
so this is with the factor in front
$$\frac{1}{(1-z)^{2r+3}}
\sum_{k=0}^{r+1} 
\left\langle\!\! \left\langle r+1 \atop k
\right\rangle\!\! \right\rangle
z^k$$
and the induction goes through.
 Now to see that ${n+r\brace n}$ is a polynomial in $n$ of degree
$2r$ we extract the coefficient on  $[z^n]$ of $Q_r(z)$ to get
$$\sum_{k=0}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
{2r+n-k\choose 2r}
= \frac{1}{(2r)!} 
\sum_{k=0}^r
\left\langle\!\! \left\langle r \atop k
\right\rangle\!\! \right\rangle
(n+2r-k)^{\underline{2r}}.$$
The  sum terms  are  products of  $2r$  linear terms  in  $n$ times  a
coefficient that does not depend  on $n$ (Eulerian number) and neither
does the range of the sum (finite, $r+1$ terms) and we have the claim.
The coefficient on $n^{2r}$ is
$$\frac{1}{(2r)!} \sum_{k=0}^r \left\langle\!\!  \left\langle r \atop k
\right\rangle\!\! \right\rangle = \frac{1}{(2r)!} (2r-1)!!
= \frac{1}{(2r)!} \frac{(2r)!}{2^r r!} = \frac{1}{2^r r!} \ne 0.$$
A: Hint:
Recall the recurrence $$S(n+1,k) = k S(n,k) + S(n,k-1).$$
Then for each $r$ we have
$$S(n+r, n) = n S(n+r-1,n) + S(n+r-1,n-1)$$
Can you use induction (on $n + r$, say) to write this as a polynomial of degree $2r$?

I hope this helps ^_^
A: 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.
