Combinatorial proof of Stirling Numbers of the second kind

Question

I need a combinatorial proof of the identity below:

$S(n,k)=\sum_{i=k-1}^{n-1}S(i,k-1)k^{(n-1)-i}$, where S(n,k) denotes Stirling number of the second kind.

I was trying to prove this in a similar way to the combinatorial proof of the identity below:

$S(n,k)=kS(n-1,k)+S(n-1,k-1)$

$S(n-1,k)$ = Number of ways to make 'n' as a singleton in [n], and partition remaining n-1 elements into k-1 blocks.

$kS(n-1,k)$ = Number of ways to make k partitions when 'n' is not a singleton, we first partition [n-1] into k blocks, and put 'n' into any of these k blocks.

I wanted to extend this idea, but I have no idea how to do this. Please help me.

Answer 1

First of all, here is a non-combinatorial proof of your identity. We repeatedly apply the recurrence relation $S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)$, each time applying it to the $S(n-1,k)$ part. Here are the first three steps of what I mean: $$ \begin{align} S(n,k) &=S(n-1,k-1)+k\cdot \color{blue}{S(n-1,k)} \\&=S(n-1,k-1)+k\Big(S(n-2,k-1)+k\cdot \color{blue}{S(n-2,k)}\Big) \\&=S(n-1,k-1)+k\Big(S(n-2,k-1)+k\cdot \Big(S(n-3,k-1)+k\cdot \color{blue}{S(n-3,k)}\Big)\Big) \\&=\vdots \end{align} $$ If you apply that all the way down, and then distribute all products, the result is exactly $\sum_i k^i S(n-1-i,k-1)$, which is equivalent to the summation in your question.

How can we turn this into a combinatorial proof? Well, we repeatedly applied the identity $S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)$, which itself has a combinatorial proof, so chaining all of those bijections together should give a bijective proof of your identity.

When you do this, here is the bijection that you get. To prove that $S(n,k)=\sum_{i=1}^{} S(i,k)k^{n-1-i}$, we answer the following question:

Given a partition $P$ of $\{1,\dots,n\}$ into $k$ unlabeled parts, define $f(P)$ to be the largest number $j$ such that the numbers $\{1,\dots,j\}$ do not span all $k$ of the parts (i.e., such that some part contains none of $\{1,\dots,j\}$). Given $i\in \{k-1,k,\dots,n-1\}$, for how many partitions does $f(P)=i$?

We will prove that the answer to this is $S(i,k-1)k^{n-1-i}$, so summing over $i$ proves your identity.

If $f(P)=i$, then the numbers $\{1,\dots,i\}$ must span exactly $k-1$ parts. The number of ways to place the numbers $\{1,\dots,i\}$ is therefore $S(i,k-1)$. Then, $i+1$ must be in a different part from each of the numbers in $\{1,\dots,i\}$. Finally, for the $n-1-i$ numbers in $\{i+2,i+3,\dots,n\}$, they must each be independently placed in one of the $k$ parts, which can be done in $k^{n-1-i}$ ways.