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.

  • 0
    There *is* indeed a proof of that equality. I am pretty sure that is not what you wanted to know, though... :)2011-12-15
  • 0
    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.2011-12-15
  • 0
    Oh, thanks Dimitrije. I downloaded a copy of enumerative combinatorics when it was up for a free, and took a look. Thanks for the reference.2011-12-15
  • 2
    you could also copy the proof here, so others can benefit2011-12-15
  • 1
    You'll want to look up Stirling numbers.2011-12-15
  • 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.2011-12-15

2 Answers 2