Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

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.

share|improve this answer
add comment

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].$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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