# Recursive formula for the number of $n$-permutations with $k$ cycles

Let $n$ and $k$ be a positive integers satisfying $n\geq k$, then

$$c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)$$

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?

Edit:

The paragraph before he finishes his proof.

• Putting $n$ in front of everything in a cycle gives the same cycle as putting it after everything in the cycle, right? – Gerry Myerson Apr 10 '15 at 9:39
• @GerryMyerson: Please see the edit. – Salech Rubenstein Apr 10 '15 at 10:18
• I see it, and I ask the same question that I asked before I saw it. But I'll be specific. Suppose you want to stick $4$ into $(1\ 2\ 3)$. You might worry that you have to stick it in $4$ different places: $(4\ 1\ 2\ 3),(1\ 4\ 2\ 3),(1\ 2\ 4\ 3),(1\ 2\ 3\ 4)$. But isn't $(4\ 1\ 2\ 3)$ equal to $(1\ 2\ 3\ 4)$? – Gerry Myerson Apr 10 '15 at 12:24
• I see it now. Thanks! – Salech Rubenstein Apr 10 '15 at 13:31