Stirling Numbers of the Second Kind $ \sum_{j= m}^n {j \brace m} (m+1)^{n-j} = {n+1\brace m+1} $

Question

I am trying to proof some identies from concrete mathmatics p 265. But i cant get nowhere. What i have found out its a recurrence, in the Stirling Numbers Triangle, its a vertical one. I get what it means, e.g. n=4 m=2 the Number of Partitioning 5 Elements into 4 Partitions ${5 \brace 3}$ can be created from from $ {2 \brace 2}*(2+1)^2 + {3 \brace 2}*(2+1)^1 + {4 \brace 2}(2+1)^0 $ but i cant interprete combinatorically the $(2+1)^2,(2+1)^1, (2+1)^0$. Any ideas. It sould also work with Induction but,....well there are 2 pages of identities, i am not sure what to choose.

Answer 1

Starting from the LHS we write with $n\ge m$ and an Iverson bracket

$$\sum_{j=m}^n {j\brace m} (m+1)^{n-j} = \sum_{j\ge m} {j\brace m} (m+1)^{n-j} [[j\le n|j\ge 0]] \\ = \sum_{j\ge m} {j\brace m} (m+1)^{n-j} [z^n] \frac{z^j}{1-z} \\ = [z^n] \frac{1}{1-z} \sum_{j\ge m} {j\brace m} (m+1)^{n-j} z^j \\ = [z^n] \frac{(m+1)^n}{1-z} \sum_{j\ge m} {j\brace m} \frac{z^j}{(m+1)^j}.$$

Recall the OGF

$$\sum_{j\ge m} {j\brace m} x^j = \prod_{r=1}^m \frac{x}{1-rx}$$

which yields for the present case

$$(m+1)^n [z^n] \frac{1}{1-z} \prod_{r=1}^m \frac{z/(m+1)}{1-rz/(m+1)} \\ = [z^n] \frac{1}{1-(m+1)z} \prod_{r=1}^m \frac{z}{1-rz} = [z^{n+1}] \frac{z}{1-(m+1)z} \prod_{r=1}^m \frac{z}{1-rz} \\ = [z^{n+1}] \prod_{r=1}^{m+1} \frac{z}{1-rz} = {n+1\brace m+1}.$$

This is the claim.

Answer 2

Let see, $n+1\brace m+1$ means that you take $n+1$ elements and you partition them in $n+1$ disjoint and non empty blocks. Denote the partitions in the following way $${[n+1]\brace m+1}=\{\pi \vdash [n+1]:|\pi|=m+1\},$$ the set of partitions. Given a partition $\pi ,$ let $j$ the maximum integer such that there is not block $B\in \pi$ such that $\{n+1,k\}\subseteq B,$ hence $\pi = (\pi _{[j]},f:[n]\setminus [j+1]\longrightarrow [m+1]),$ where $\pi _{[j]}$ is the partition $\pi$ but restricted to the set $[j]$ =because we know that $j+1$ has to be in the same block as $n+1$ and the function sends an element to one of the blocks(notice that blocks can be ordered by lexicografic order.) and hence $${[n+1]\brace m+1} = \bigcup _{j = m}^{n-1}{[j]\brace m}\times [m+1]^{n-(j+1)}$$