Combinatorial proof for a Stirling identity

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!

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