Let $n$ and $k$ be a positive integers satisfying $n\geq k$, then
where $c(n,k)$ denotes the number of $n$-permutations with $k$ cycles.
The proof of this theorem goes like this: we take the entry $n$ and ask if that entry form a cycle by itself or not, if it does, then we get the number $c(n-1,k-1)$. OK, elsewhere, $n$ does not form a cycle by itself, then we have the remaining $n-1$ entries that must form $k$ cycles. The $k$ cycles can be formed in $c(n-1,k)$ ways and in every such permutation we insert entry $n$ after each element. This multiplies the number of possibilities by $n-1$, and we get $(n-1)c(n-1,k)$ such permutations.
My question is, because we need insert the entry $n$ to all $c(n-1,k)$ permutations, and in every such permutation we have $n-1$ ways of doing that, what insures that, with inserting $n$ after each element(instead inserting it before each element) we won't miss any permutation?
The paragraph before he finishes his proof.