Stirling numbers

Question

Let $c \binom n k$ denote the number of permutations in $S_n$ with $k$ cycles.

Find formulas for $c \binom n {n-2}$ and for $c \binom n 2$, and double-check that they hold for $n = 4$.

Answer 1

Hint: both of these are susceptible to direct computation. For the first, if $n$ is large you will have to have many cycles with just one element. If you think about that, there aren't many patterns to break the $n$ elements among $n-2$ cycles-how many? Then count the ways to assign the $n$ elements. For the second, you have to break $n$ into two summands-how many ways to do that? Again, how many ways to assign the elements. What do you need to be careful of if $n$ is even?