Score Sequence
المؤلف:
Comtet, L.
المصدر:
Problem 21 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel
الجزء والصفحة:
...
10-3-2022
2124
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 ![<span style=]()
{0,1}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline8.svg" style="height:22px; width:43px" />. For 
, the two possible sequences are ![<span style=]()
{0,1,2}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline10.svg" style="height:22px; width:64px" /> and ![<span style=]()
{1,1,1}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline11.svg" style="height:22px; width:64px" />. And for 
, the four possible sequences are ![<span style=]()
{0,1,2,3}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline13.svg" style="height:22px; width:85px" />, ![<span style=]()
{0,2,2,2}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline14.svg" style="height:22px; width:85px" />, ![<span style=]()
{1,1,1,3}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline15.svg" style="height:22px; width:85px" />, and ![<span style=]()
{1,1,2,2}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline16.svg" style="height:22px; width:85px" /> (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 ![<span style=]()
{1,1,2,3,3}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline23.svg" style="height:22px; width:106px" /> and three with ![<span style=]()
{1,2,2,2,3}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline24.svg" style="height:22px; width:106px" />.
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."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
