9
$\begingroup$

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.

  • 1
    Let me second yoyo's suggestion. It's OK - in fact, it's encouraged - to $p$ost 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.2011-12-15

2 Answers 2

5

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.

3

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