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.