Score Sequence

The score sequence of a tournament is a monotonic nondecreasing sequence of the outdegrees of the graph vertices of the corresponding tournament graph. Elements of a score sequence of length  therefore lie between 0 and , inclusively. Score sequences are so named because they correspond to the set of possible scores obtainable by the members of a group of  players in a tournament where each player plays all other  players and each game results in a win for one player and a loss for the other. (The score sequence for a given tournament is obtained from the set of outdegrees sorted in nondecreasing order, and so must sum to , where  is a binomial coefficient.)

For example, the unique possible score sequences for  is . For , the two possible sequences are  and . And for , the four possible sequences are , , , and  (OEIS A068029).

Landau (1953) has shown that a sequence of integers  () is a score sequence iff

for , ..., , where  is a binomial coefficient, and equality for

(Harary 1994, p. 211, Ruskey).

The number of distinct score sequences for , 2, ... are 1, 1, 2, 4, 9, 22, 59, 167, ... (OEIS A000571). A score sequence does not uniquely determine a tournament since, for example, there are two 4-tournaments with score sequence  and three with .

REFERENCES

Comtet, L. Problem 21 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, p. 123, 1974.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 207-208 and 210-211, 1994.

Landau, H. G. "On Dominance Relations and the Structure of Animal Societies, III. The Condition for a Score Structure." Bull. Math. Biophys. 15, 143-148, 1953.

Moon, J. W. Topics on Tournaments. New York: Holt, p. 68, 1968.Narayana, T. V. and Best, D. H. "Computation of the Number of Score Sequences in Round-Robin Tournaments." Canad. Math. Bull. 7, 133-136, 1964.

Ruskey, F. "Information on Score Sequences." http://www.theory.csc.uvic.ca/~cos/inf/nump/ScoreSequence.html.Ruskey, F.; Cohen, R.; Eades, P.; and Scott, A. "Alley CATs in Search of Good Homes." Congres. Numer. 102, 97-110, 1994.

Sloane, N. J. A. Sequences A000571/M1189 and A068029 in "The On-Line Encyclopedia of Integer Sequences."