I am struggling with the following question from an assignment for an introductory course to combinatorics.
Show, by means of a combinatorial argument, that the following holds:
\begin{aligned}
{n+1 \brace k+1}&=\sum_{r=k}^{n}\binom{n}{r} {r \brace k}
\end{aligned}
Using the familiar identity
\begin{equation}
{n \brace k}={n-1 \brace k-1}+k{n \brace k-1}
\end{equation}
I am able to show algebraically that
\begin{equation}
{n+1 \brace k+1}=\sum_{m=k}^{n}(k+1)^{n-m}{m \brace k}.
\end{equation}
In doing this, I hoped to be able to introduce binomial coefficients in order to determine whether the recursive definition of the Stirling number of the second kind would be conducive to an algebraic proof. Unfortunately, the exponential terms remained even after substituting
\begin{equation}
(k+1)^{n-m}=\sum_{i=1}^{n-m}\binom{n-m}{i}k^{i}
\end{equation}
which would give the definition:
\begin{equation}
{n+1 \brace k+1}=\sum_{m=k}^{n} \left[ \sum_{i=1}^{n-m}\binom{n-m}{i}k^{i} \right] {m \brace k}
\end{equation}
Of course, if I had been successful, I hoped to convert this understanding into a modification of the combinatorial proof for the recursive identity, $S(n,k)=S(n-1,k-1)+kS(n-1,k)$ (where there are two cases: one in which $n$ is a singleton and the other in which $n \in A$, where $|A|>1$).
If anyone has any recommendations or hints as to how to conduct the combinatorial proof (or even the algebraic one, which I am personally curious about), I would greatly appreciate the help!
Thank you
Best Answer
Start by typesetting the claim using standard conventions. We seek to show that $${n+1 \brace k+1} = \sum_{m=k}^n {n\choose m} {m\brace k}.$$
The combinatorial proof is extremely straightforward. The left side is the number of partitions of a set of $n+1$ distinguishable items into $k+1$ indistinguishable subsets. (Permutation group $S_{k+1}$ and no positioning on the subsets -- a set of sets.) The right side counts the same statistic. Suppose we have a partition into $k+1$ subsets and the item with the label $n+1$ has gone into a subset of size $n-m+1$. (There are $n-m$ other elements in this subset.) Then we must have chosen $m$ elements from the other $n$ items for the other $k$ subsets and partitioned those $m$ items into $k$ subsets, giving a contribution of $${n\choose m} {m\brace k}.$$ The sum counts all possible total subset sizes for the subsets not containing $n+1$, starting at $k$ because none of the subsets may be empty.
The algebraic proof uses exponential generating functions. Recall that partitions into subsets have the following combinatorial specification: $$\mathfrak{P}(\mathfrak{P}_{\ge 1}(\mathcal{Z})).$$ This immediately implies that the generating function of the Stirling numbers of the second kind is $$ G(z, u) = \exp(u(\exp(z)-1)).$$ Now we have $${n+1 \brace k+1} = (n+1)! [z^{n+1}] [u^{k+1}] \exp(u(\exp(z)-1)) \\= (n+1)! [z^{n+1}] \frac{(\exp(z)-1)^{k+1}}{(k+1)!}.$$ This last term is $$(n+1)! \frac{1}{n+1} [z^n] \left(\frac{(\exp(z)-1)^{k+1}}{(k+1)!}\right)'\\ = n! [z^n] \frac{(k+1)(\exp(z)-1)^k}{(k+1)!} \exp(z) = n! [z^n] \exp(z) \frac{(\exp(z)-1)^k}{k!}.$$ Expanding the product of the two exponentials this yields $$n! \sum_{m=0}^n \frac{1}{(n-m)!} [z^m] \frac{(\exp(z)-1)^k}{k!} = \sum_{m=0}^n \frac{n!}{m! (n-m)!} m! [z^m] \frac{(\exp(z)-1)^k}{k!} \\= \sum_{m=0}^n \frac{n!}{m! (n-m)!} {m \brace k} = \sum_{m=k}^n {n\choose m} {m \brace k}.$$
Observe that the combinatorial and the algebraic proof are very similar.