I need to verify the following combinatorial proof:
$$\sum_{i=0}^n {{n}\choose{i}} { n-i\brack k} i! = { n+1 \brack k+1}$$
On the RHS we count all possible permutations of $n+1$ elements with $k+1$ cycles.
On the LHS we set aside the last element ($n+1$), then we choose $i$ elements from remaining $n$ elements. After that we count all possible permutations of $n-i$ elements (those which were not chosen) with $k$ cycles. Then we create the last cycle with the chosen elements in one of $(i-1)!$ ways (because the smallest of them must be on the first place). After that we put the element that we set aside at the beginning in one of $i$ places (after one of $i$ elements) in the last cycle. Therefore we get $(i-1)! \cdot i = i!$.
Is that correct?