The question is to prove the identity

$$ {n+1\brace k+1}=\sum_i \binom{n}{i}{i\brace k}\tag{1} $$

via a combinatorial proof and an algebraic proof. The question is from Aigner's A Course in Enumeration.

The braces indicate Stirling numbers of the second kind. I have managed to prove the identity using the polynomial method (which I will show below), but have not made much progress on the combinatorial proof.

My attempt: The left hand side represents the number of ways to partition an $n+1$ element set (say $[n+1]=\{1,\dotsc, n+1\}$) into $k+1$ sets. Each of the summands on the right hand side represents choosing $i$ elements where $k \leq i\leq n$ from $[n]$ and then partitioning them into $k$ sets. There is probably some sort of classification of the partition of an $n+1$ element set in to $k+1$ sets but I am not seeing it.

Algebraic Proof:

We expand $(x+1)^n$ in two different ways. First, note that $$ (x+1)^n=\sum_{i=0}^n\binom{n}{i}x^i=\sum_{i=0}^n\binom{n}{i}\sum_{k=0}^i {i\brace k} (x)_k=\sum_{k=0}^n(x)_k\left[\sum_{i=k}^n \binom{n}{i}{i\brace k} \right]\tag{2} $$ by the binomial theorem where $(x)_k$ is the falling factorial of length $k$. For the second way write $(x+1)^n$ as $$ \sum_{k=0}^n{n\brace k}(x+1)_{k} =\sum_{k=0}^n{n\brace k}[(x)_k+k(x)_{k-1}]= \sum_{k=0}^n\left[{n\brace k}+(k+1){n\brace k+1}\right](x)_k\tag{3} $$ and conclude using the recurrence relation for Stirling numbers.


Your algebriac proof is fine. For the Combinatorial proof consider the set that conatins the element $n+1$.

Choose $n-i$ elements from $[n]$ and create a block containing $n+1$ and the $n-i$ chosen elements. Now partition the final $i$ elements into $k$ blocks. Thus \begin{eqnarray*} {n+1\brace k+1}=\sum_{i=k}^{n} \binom{n}{i}{i\brace k}. \end{eqnarray*}


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.