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.

-
There is indeed a proof of that equality. I am pretty sure that is not what you wanted to know, though... :) –  Mariano Suárez-Alvarez Dec 15 '11 at 17:41
There are two proofs of this result in Richard Stanley, Enumerative Combinatorics v.1 on page 19. I can print one (or both) as an answer if you'd like. –  Dimitrije Kostic Dec 15 '11 at 17:42
you could also copy the proof here, so others can benefit –  yoyo Dec 15 '11 at 18:35
You'll want to look up Stirling numbers. –  Ｊ. Ｍ. Dec 15 '11 at 19:25
Let me second yoyo's suggestion. It's OK - in fact, it's encouraged - to post an answer to your own question and then, if no one has objected to it, accept the answer. It clears up the unanswered questions list. –  Gerry Myerson Dec 15 '11 at 23:23
show 1 more comment

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.

-
This one can also be done using exponential generating functions. Start from the marked species $$\mathcal{Q} = \mathfrak{P}(\mathcal{U}\mathfrak{C}(\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.$$