I was reading a little bit about Galois theory, and read that some computer algebra software try to compute Galois groups by finding cycle types.
Anyway, this led me to a curious question. If I fix some $n$, and let $c(n,k)$ by the number of permutations in $S_n$ with $k$ cycles, then what is the generating function $$ \sum_k c(n,k)x^k? $$ I browsed around, and I think it's something like $$ \sum_k c(n,k)x^k=x(x+1)\cdots(x+n-1) $$ but I don't understand why. Is there a proof of why those expressions are equal? Thanks.