Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is well-known that the number of acyclic orientations of $K_n$ is $n!$. Does anybody know of a combinatorial argument for this fact which uses the identity: $$n!=\sum_{k=1}^ns(n,k),$$ where the $s(n,k)$ are Stirling numbers of the first kind? If such a thing exists; what do the different Stirling numbers correspond to exactly?

I would also be interested in any other information or references linking Stirling numbers with acyclic orientations. And failing all this, if anybody knows of any other nice combinatorial arguments (that is, not involving the evaluation of the chromatic polynomial at $-1$) for the numbers of acyclic orientations of complete graphs then I would be interested to hear them.

share|improve this question
2  
An acyclic ordering on a complete graph is just the same think as a total order on the vertices. Edges point from small to big. There are clearly n! of these. So it seems you just want to interpret your identity in terms of linear orders. –  Benjamin Steinberg Jun 25 '12 at 16:49
    
More interesting is the generalization to any graph, due to Greene and Zaslavsky. See Corollary 7.4 of their paper at vulcan.math.binghamton.edu/zaslav/Tpapers/iwn.tams1983.pdf. –  Richard Stanley Jun 25 '12 at 23:09
add comment

1 Answer

hmmm...seems I was being lazy. Did that thing where you get up to do something else and the answer suddenly seems obvious. You just need to label the vertices of each acyclic orientation according to the order it dictates, and choose one to be your "identity". The others are clearly then just permutations of the labels with cycle numbers corresponding to the k in each s(n,k). Thanks for your help Benjamin.

Writing this as an answer so it can be marked as resolved (if I can accept my own answer!).

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.