Stirling number relation

Question

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$?

Answer 1

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.$$

Answer 2

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 ^_^

Answer 3

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.