Generating function for permutations in $S_n$ with $k$ cycles. 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.
 A: You are looking at permutations of $n$ and each cycle contributes a factor $x$.
Now, when you place the first element, there is only one possibility, it starts a cycle, this gives $x$.
When you place the second element, it either starts a new cycle giving $x$ or it is placed in the cycle of the first element, this gives $x+1$
When you place element $k$, it either starts a new cycle giving $x$ or it is placed as image of one of the elements that are already there, this gives $x+k-1$.
So, in total, you get the product on the right-hand side.
A: This one can also be done using exponential generating functions. Start from the marked combinatorial class $$\mathcal{Q} = \def\textsc#1{\dosc#1\csod}\def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}(\mathcal{U}\times\textsc{CYC}(\mathcal{Z}))$$ which represents permutations marked according to the number of cycles.
This immediately produces the generating function
$$Q(z, u) = \exp\left(u\log\frac{1}{1-z}\right)$$
from which it follows that
$$\left[n\atop k\right] = n! [z^n] [u^k] \exp\left(u\log\frac{1}{1-z}\right)$$
which implies that
$$\sum_{k=1}^n \left[n\atop k\right] x^k = 
n! [z^n] \exp\left(x\log\frac{1}{1-z}\right)
= n! [z^n]  \left(\frac{1}{1-z}\right)^x.$$
To conclude apply the Newton binomial to get
$$n! {n+x-1\choose n} = n! \frac{(x+n-1)(x+n-2)\cdots x}{n!}
\\ = (x+n-1)(x+n-2)\cdots(x+1)x.$$
