How to prove the following combinatorially ?

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

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.

  • $\begingroup$ 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. $\endgroup$ – David Holden Mar 9 '15 at 9:14
  • $\begingroup$ @David: You’re welcome. $\endgroup$ – Brian M. Scott Mar 9 '15 at 9:15
  • $\begingroup$ 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}$$ ? $\endgroup$ – Guest 123 Mar 9 '15 at 12:10
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Mar 9 '15 at 20:49
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Guest 123 Mar 10 '15 at 4:59
  • $\begingroup$ I was aware of that but I posted anyway for variety's sake. $\endgroup$ – Marko Riedel Mar 10 '15 at 5:01
  • $\begingroup$ @Guest123 It appears that the proof by Brian M. Scott is not difficult and rewards detailed examination. $\endgroup$ – Marko Riedel Mar 10 '15 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.