Number of ways we can choose a permutation from $Sn$ and then some subset of the set of its cycles? The answer in my book goes as follows:
If there is k elments in chosen cycles then number of choices is ${n \choose k}k!(n-k)!$. So the answer is $(n+1)!$
Obviously ${n \choose k}k!(n-k)!=n!$ and $\sum_1^n n! =(n+1)!$ so that part is clear.
What I don't get is why we have ${n \choose k}k!(n-k)!$ for given k
If we have k elements in chosen cycles we choose those in ${n \choose k}$ ways.Then we make a permutation out of those k elements in $k!$ ways. Then we are supposed to count all possible subsets of all possible cycle sets and I have no idea how is that number even remotely connected with $(n-k)!$
I know this question doesn't show much research but I tried doing it alone  and couldn't think of anything and then I've seen the answer and spent last 2 hours trying to make some  sense out of it.
Any hints?
 A: There’s a symmetry here between the chosen cycles and the cycles not chosen – it doesn’t make a difference which ones you call “chosen” and which ones you call “not chosen” – in either case, their elements must be permuted among themselves, and that can be done in $k!$ ways for the chosen ones and in $(n-k)!$ ways for the ones not chosen.
You can also derive this count by induction. Let’s call a  permutation together with a subset of its cycles a configuration. Clearly there are $(1+1)!=2$ configurations for $S_1$. Now assume that there are $n!$ configurations for $S_{n-1}$ and consider in how many ways you can add an $n$-th element $a$ to one of them. You can put $a$ in a cycle by itself and either include that cycle among the chosen cycles or not, which makes $2n!$ configurations; or you can add $a$ to an existing cycle by picking one of the $n-1$ elements and writing $a$ after it in the cycle notation, which makes $(n-1)n!$ configurations. So the total is $2n!+(n-1)!n!=(n+1)n!=(n+1)!$.
