I am asked to use combinatorial proof to prove a Stirling identity:
$${n+1\brack m} = \sum_{k=0}^n {n-k\brack m-1} n^{\underline{k}}$$
Basically I know that the LHS is the number of permutations 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!
You are right, the RHS is easily interpreted as the number of permutations of $n+1$ into $m$ cycles.
Now consider the cycle that contains the element $n+1$ and consists of $k+1$ elements (in toto), there will be $m-1$ other cycles containing $n-k$ 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 ${n-k \brack m-1}$ ways. Now observe that $k$ can range over $1 ,\cdots ,n$ so $$ {n+1 \brack m} = \sum_{k=0}^n {n-k \brack m-1} n^{\underline{k}}. $$