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

In a round-robin tournament with $n$ teams, each team plays every other team exactly once. Thus, there are $n(n-1)/2$ total games played. How many different standings can result? By a "standing" I mean the ordered sequence $(W_1, \ldots, W_n)$ where $W_i$ is the number of wins by the $i$th player. Assume that no game ends in a tie.

I wrote a program to calculate this sequence. For $n$ up to 13, it agrees with the number of forests on $n$ labeled nodes, which is Sequence A001858 in the OEIS. But I can't see the correspondence between tournament standings and forests with labeled nodes. Can anyone explain this?

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

The bijection between score vectors and forests on labeled nodes is due to Kleitman and Winston. (This paper)

A small clarification, your question about the cardinalities being equal was answered by Stanley and Zaslavsky, see Stanley's paper "Decomposition of rational convex polytopes", but the proof was not bijective.

share|improve this answer
2  
The polytope of win vectors, by J. E. Bartels, J. Mount and D. J. A. Welsh, is also accessible at springerlink.com/content/wr13217220x05726/fulltext.pdf and also speaks to this. –  ABh Aug 24 '10 at 2:21
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.