Generating function for permutations in $S_n$ with $k$ cycles.

Question

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.

Answer 1

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.

Answer 2

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.$$