# 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... :) Dec 15, 2011 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. Dec 15, 2011 at 17:42
• you could also copy the proof here, so others can benefit
– yoyo
Dec 15, 2011 at 18:35
• You'll want to look up Stirling numbers. Dec 15, 2011 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. Dec 15, 2011 at 23:23

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