Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
you could also copy the proof here, so others can benefit –  yoyo Dec 15 '11 at 18:35
1  
You'll want to look up Stirling numbers. –  J. M. Dec 15 '11 at 19:25
1  
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

2 Answers 2

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.