# Combinatorial proof of Stirling Number Identity (First Kind)

For $m,n\ge 0$,

$$\sum^m_{k=0} (n+k)\left[{n+k}\atop{k}\right]={{m+n+1}\brack m}\;.$$

I need to prove this combinatorially. I know the RHS counts the number of $m+n+1$ permutations with $m$ cycles. I'm stuck on how to show the LHS does so too.

-
Right-click on the displayed formula to see two ways to produce the Stirling brackets. – Brian M. Scott Apr 26 '13 at 23:42
Thanks, Brian! Any ideas on how to prove it? – Cindy G Apr 26 '13 at 23:58

Suppose that $\pi$ is a permutation of $[m+n+1]$ with $m$ cycles. Let $\ell$ be the largest element of $[m+n+1]$ that is not in a $1$-cycle of $\pi$. Then $\pi$ is obtained from a permutation $\sigma$ of $[\ell]$ by appending $1$-cycles $(\ell+1)(\ell+2)\ldots(m+n+1)$, where $\ell$ is not in a $1$-cycle of $\sigma$, and $\sigma$ has $$m-\Big((m+n+1)-\ell\Big)=\ell-n-1$$ cycles. This means that $\sigma$ can be obtained from a permutation $\tau$ of $[\ell-1]$ with $\ell-n-1$ cycles by inserting $\ell$ into some cycle of $\tau$.

A little thought shows that $n+2\le\ell\le m+n+1$, so $\ell-1$ ranges from $n+1$ through $n+m$. Fix $\ell-1$ in this range, and let $\tau$ be any permutation of $[\ell-1]$ with $\ell-n-1$ cycles. There are $\ell-1$ ways to extend $\tau$ to a permutation $\sigma$ of $[\ell]$ with $\ell-n-1$ cycles by inserting $\ell$ into a cycle of $\tau$. This $\sigma$ can then be extended uniquely to a permutation $\pi$ of $[m+n+1]$ with $$(\ell-n-1)+\Big((m+n+1)-\ell\Big)=m$$ cycles such that $\ell$ is the largest element of $[m+n+1]$ not in a $1$-cycle. Summing over $\ell$, we have

$${{m+n+1}\brack m}=\sum_{\ell=n+2}^{n+m+1}(\ell-1){{\ell-1}\brack{\ell-n-1}}\;.$$

Make an appropriate change of index, and you’ll have the result.

Added: To see how I came up with this, it may help to realize that it’s just a generalization of the combinatorial proof of the recurrence

$${{n+1}\brack k}=n{n\brack k}+{n\brack{k-1}}$$

that is given here, among other places.

-

For the sake of completeness we present a proof of the basic recurrence using generating functions. The bivariate exponential generating function of the unsigned Stirling numbers of the first kind is given by $$G(z, u) = \exp\left(u \log\frac{1}{1-z}\right).$$

It follows that the exponential generating function of $n\left[n\atop k\right]$ is given by $$H(z, u) = z \frac{\partial}{\partial z} G(z, u) = z\exp\left(u \log\frac{1}{1-z}\right) u (1-z) (-1) \frac{1}{(1-z)^2} (-1) \\= u \frac{z}{1-z}\exp\left(u \log\frac{1}{1-z}\right).$$

The RHS of the basic recurrence is thus given by $$n\left[n\atop k\right] + \left[n\atop k-1\right] = n![z^n u^k] H(z, u) + n![z^n u^{k-1}] G(z, u) \\ = n![z^{n+1} u^k] z H(z, u) + n![z^{n+1} u^k] z u G(z, u) \\ = n![z^{n+1} u^k] \exp\left(u \log\frac{1}{1-z}\right) \left(u \frac{z^2}{1-z} + zu\right) \\ = n![z^{n+1} u^k] \exp\left(u \log\frac{1}{1-z}\right) \frac{u z}{1-z} = n![z^{n+1} u^k] H(z, u) \\= n! \frac{(n+1)}{(n+1)!} \left[n+1\atop k\right] = \left[n+1\atop k\right].$$

-