I am asked to use combinatorial proof to prove a sterling identity:

$$\begin{bmatrix} n+1 \\ m \end{bmatrix} = \sum_{k=0}^n \begin{bmatrix} n-k \\ m-1 \end{bmatrix} n^{\underline{k}}$$

Basically I know that the LHS is the number of permuations of an $n+1$ set with $m$ cycles, but I really don't know how to get the LHS. I fail to visualize this! Any help will be much appreciated, thank you very much!

  • $\begingroup$ Hint: First pick the cycle that contains $n+1$; then draw the rest of the proverbial owl. $\endgroup$ – darij grinberg Mar 12 '18 at 8:23
  • $\begingroup$ Do you mean to say $$\binom {n+1}{m}=\sum_{k=0}^n \binom {n-k}{m-1}\binom {n}{k}$$ $\endgroup$ – Darkrai Mar 12 '18 at 8:25
  • $\begingroup$ No it's a stirling cycle $\endgroup$ – bluemuse Mar 12 '18 at 14:23

You are right, the RHS is easily interpreted as the number of permutations of $n+1$ into $k$ cycles.

Now consider the $m^{th}$ cycle to begin with the element $n+1$ and contain $k+1$ elements \begin{eqnarray*} \underbrace{(\cdots)\cdots (\cdots)}_{n-k \text{ elements in } m-1 \text{ cycles}} (n+1 \cdots) \end{eqnarray*} the last $k$ elements of the last cycle can be chosen in $n(n-1) \cdots (n-k+1)=n^{\underline{k}}$ ways and the first $k$ cycles can be chosen in $\begin{bmatrix} n-k \\ m-1 \end{bmatrix}$ ways. Now observe that $k$ can range over $1 ,\cdots ,n-m$ so \begin{eqnarray*} \begin{bmatrix} n+1 \\ m \end{bmatrix} = \sum_{k=0}^n \begin{bmatrix} n-k \\ m-1 \end{bmatrix} n^{\underline{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.