Combinatorial proof verification: $\sum_{i=0}^n {{n}\choose{i}} { n-i\brack k} i! = { n+1 \brack k+1}$

Question

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?

Answer 1

This combinatorial proof is correct. However I would rewrite it a bit. On the LHS we sum over the length $i + 1$ of a cycle containing $n + 1$. Then we select $i$ other elements of this cycle, make other $k$ cycles of $n - i$ elements, and place the selected $i$ elements before $n + 1$ in this cycle. Note that we don't specify whether it was the $1$st cycle, or the $2$nd one, or the $k + 1$st one, all we know is that this cycle contains $n + 1$, and such a cycle always should exist. (The order of cycles actually doesn't matter at all.)