Number of k-products of disjoint cycles in the symmetric group S(n)

Question

Suppose that $S(n)$ denotes the group of all permutations of the set $\{1,2,...,n\}$ with the usual composition operation. Is there any formula or expression for $n(k)$, where $n(k)$ denotes the number of elements of $S(n)$ that can be written as the product of exactly $k$ disjoint cycles ($k$ lies between $1$ and $n$)? Also, a proof will be highly appreciated.

Answer 1

The Stirling coefficient of the first kind.

The recursion is $S^{(n)}_k=S^{(n-1)}_{k-1}+(n-1)S^{(n-1)}_{k}$

To see why this recursion holds look at the integer $n$, the first term in the sum counts the permutations where $n$ is a fixed point (It is the only element in the cycle). The second term counts those permutations in which $n$ is not a fixed point. How, exactly? Imagine you have a permutation and you write it down in it's canonical factorization (So that each cycle is ordered according to it's least element, and the cycles themselves are in order). Then if you remove the number $n$ from the sheet of paper what you obtain is a permutation with $k$ cycles and $n-1$ terms (There are $k$ cycles beacuse $n$ was not a fixed point). Moreover given a permutation with $k$ cycles and the numbers $1$ through $n-1$ there are $n-1$ places where you can place the $n$ element to create a permutation with $k$ cycles and the numbers $1$ through $n$(respecting the parenthesis of course).