# Stirling numbers: Combinatorial proof of an identity

How to prove the following combinatorially ?

$${n+1 \brace k+1}=\sum_{m=k}^{n}(k+1)^{n-m}{m \brace k}.$$

My question is how are only ( n - m ) elements being considered to be placed on the (k + 1) boxes ? And that too without any combination like n C (n - m) ?

Suppose that you have a distribution of the set $\{1,\ldots,n+1\}$ into $k+1$ identical boxes. Let $m$ be the smallest number such that the set $\{1,\ldots,m\}\cup\{n+1\}$ contains an element of every box. In other words, $m$ is the smallest number such that $\{1,\ldots,m\}$ contains an element of each of the $k$ boxes not containing $n+1$. Clearly $k\le m\le n$. How many distributions share this number $m$?

• There are ${m\brace k}$ ways to distribute the numbers $1,\ldots,m$ amongst the $k$ boxes not containing $n+1$.

• The The $n-m$ elements of $\{m+1,\ldots,n\}$ can then be distributed arbitrarily amongst the $k+1$ boxes in $(k+1)^{n-m}$ ways.

Thus, there are a total of $(k+1)^{n-m}{m\brace k}$ distributions of $\{1,\ldots,n+1\}$ into $k+1$ identical boxes that share this value of $m$, and hence

$$\sum_{m=k}^n(k+1)^{n-m}{m\brace k}$$

distributions altogether.

• thx for that nice explanation, Brian. i had the basic idea, but didn't find your neat way of convincing myself that double-counting was ruled out. – David Holden Mar 9 '15 at 9:14
• @David: You’re welcome. – Brian M. Scott Mar 9 '15 at 9:15
• Brian, thanks for taking the time to reply. You said, "There are {mk} ways to distribute the numbers 1,…,m amongst the k boxes not containing n+1." What I don't get is why don't we choose all combinations of this selection of k from n ? Why a seemingly arbitrary selection of k objects ? Shouldn't it be something like $$\binom{n}{k} * {m \brace k}$$ ? – Guest 123 Mar 9 '15 at 12:10
• @Guest123: We aren’t selecting $k$ things. We have $m$ things, where $m$ is the smallest integer such that the first $m$ things use all $k$ of the boxes not containing the $(n+1)$-st thing, and we’re counting the ways to distribute them amongst $k$ boxes. – Brian M. Scott Mar 9 '15 at 20:49
• Prof. Brian thanks again. Actually that's what I wanted to clarify as to WHY aren't we selecting those m things. It seems arbitrary. We can have any combination of these m things, so somewhere it IS indeed being taken care of. I'll try to find out how it is so. Thank you. – Guest 123 Mar 10 '15 at 4:57

By way of enrichment here is a proof using generating functions. Suppose we seek to evaluate $$\sum_{m=k}^n (k+1)^{n-m} {m\brace k} = (k+1)^n \sum_{m=k}^n (k+1)^{-m} {m\brace k}.$$

This is $$(k+1)^n \sum_{m=0}^{n-k} (k+1)^{-m-k} {m+k\brace k}$$ or $$(k+1)^{n-k} \sum_{m=0}^{n-k} (k+1)^{-m} {m+k\brace k}.$$

What we have here is $$(k+1)^{n-k} [z^{n-k}] \frac{1}{1-z} \sum_{m\ge 0} {m+k\brace k} \frac{z^m}{(k+1)^m}.$$

Now recall the OGF of Stirling numbers with fixed $k$ which was evaluated e.g. at this MSE link: $$P(z) = \sum_{m\ge 0}{m\brace k} z^m = \prod_{p=1}^k \frac{z}{1-pz}.$$ This is $$\sum_{m\ge k}{m\brace k} z^m = \sum_{m\ge 0}{m+k\brace k} z^{m+k}.$$ It follows that $$\sum_{m\ge 0}{m+k\brace k} z^{m} = \prod_{p=1}^k \frac{1}{1-pz}.$$

Substituting this into the sum yields $$(k+1)^{n-k} [z^{n-k}] \frac{1}{1-z} \prod_{p=1}^k \frac{1}{1-pz/(k+1)} \\ = (k+1)^{n-k} [z^{n-k}] \prod_{p=1}^{k+1} \frac{1}{1-pz/(k+1)} \\ = (k+1)^{n-k} [z^{n-k}] \prod_{p=1}^{k+1} \frac{k+1}{k+1-pz} \\ = (k+1)^{n+1} [z^{n-k}] \prod_{p=1}^{k+1} \frac{1}{k+1-pz}.$$

This is $$\frac{(k+1)^{n+1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \prod_{p=1}^{k+1} \frac{1}{k+1-pz} \; dz.$$

Put $z=(k+1) w$ so that $dz = (k+1)\; dw$ to get $$\frac{(k+1)^{n+1}}{2\pi i} \int_{|w|=\epsilon} \frac{k+1}{w^{n-k+1}(k+1)^{n-k+1}} \prod_{p=1}^{k+1} \frac{1}{k+1-p(k+1)w} \; dw$$ which is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{k+1}{w^{n-k+1}(k+1)^{-k}} \prod_{p=1}^{k+1} \frac{1}{k+1-p(k+1)w} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n-k+1}(k+1)^{-(k+1)}} \prod_{p=1}^{k+1} \frac{1}{k+1-p(k+1)w} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n-k+1}} \prod_{p=1}^{k+1} \frac{1}{1-pw} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{k+1}}{w^{n+2}} \prod_{p=1}^{k+1} \frac{1}{1-pw} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+2}} \prod_{p=1}^{k+1} \frac{w}{1-pw} \; dw.$$

This last integral evaluates to $${n+1\brace k+1}$$ by inspection.

• Marko, that is some proof ! Though I don't understand it, I'm sure it'll be useful for someone looking for a non-combinatorial proof. Actually I was seeking a combinatorial proof. – Guest 123 Mar 10 '15 at 4:59
• I was aware of that but I posted anyway for variety's sake. – Marko Riedel Mar 10 '15 at 5:01
• @Guest123 It appears that the proof by Brian M. Scott is not difficult and rewards detailed examination. – Marko Riedel Mar 10 '15 at 5:14