TOPICS
Search

Score Sequence


ScoreSequence

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 n therefore lie between 0 and n-1, inclusively. Score sequences are so named because they correspond to the set of possible scores obtainable by the members of a group of n players in a tournament where each player plays all other n-1 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 (n; 2), where (n; 2) is a binomial coefficient.)

For example, the unique possible score sequences for n=2 is {0,1}. For n=3, the two possible sequences are {0,1,2} and {1,1,1}. And for n=4, the four possible sequences are {0,1,2,3}, {0,2,2,2}, {1,1,1,3}, and {1,1,2,2} (OEIS A068029).

Landau (1953) has shown that a sequence of integers s_1<=s_2<=s_3<=...<=s_n (0<=s_i<=n-1) is a score sequence iff

 sum_(i=1)^ks_i>=(k; 2)

for k=1, ..., n-1, where (k; 2) is a binomial coefficient, and equality for

 sum_(i=1)^ns_i=(n; 2)

(Harary 1994, p. 211, Ruskey).

The number of distinct score sequences for n=1, 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 {1,1,2,3,3} and three with {1,2,2,2,3}.


See also

Directed Graph, Oriented Graph, Outdegree, Tournament, Tournament Matrix

Explore with Wolfram|Alpha

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."

Referenced on Wolfram|Alpha

Score Sequence

Cite this as:

Weisstein, Eric W. "Score Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ScoreSequence.html

Subject classifications