2
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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