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 {0,1}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline8.svg" style="height:22px; width:43px" />. For , the two possible sequences are {0,1,2}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline10.svg" style="height:22px; width:64px" /> and {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 {0,1,2,3}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline13.svg" style="height:22px; width:85px" />, {0,2,2,2}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline14.svg" style="height:22px; width:85px" />, {1,1,1,3}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline15.svg" style="height:22px; width:85px" />, and {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 {1,1,2,3,3}" src="https://mathworld.wolfram.com/images/equations/ScoreSequence/Inline23.svg" style="height:22px; width:106px" /> and three with {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."

اخر الاخبار

اخبار العتبة العباسية المقدسة

مجلة تسليم تدعو الباحثين والأكاديميين للمشاركة في أعدادها القادمة

المجمع العلمي يواصل إقامة محاضراته الأسبوعية في مقام الإمام المهدي (عجل الله فرجه)

جامعة الكفيل تطلق الدورة التدريبية الصيفية لطلبة كلية الهندسة التقنية

استعدادًا لزيارة الأربعين العتبة العباسية المقدسة تعقد الورشة التنسيقية الرابعة الخاصة بمراكز إرشاد التائهين

المزيد

الآخبار الصحية

دراسة علمية تكشف مفاجأة حول الأسباب الحقيقية للسمنة

دراسة: الأطباء يتجاهلون "سببا شائعا" لارتفاع ضغط الدم

نظامك الغذائي غني بالبروتين؟.. احذر هذه الآثار الجانبية

لا تتجاهلها.. أعراض تنذرك بأنك مهدد بالإصابة بالسكري

المزيد

الآخبار التكنلوجية

ISOFIX: معيار الأمان الذهبي لمقاعد الأطفال في السيارات

هل المحرك الأكبر دائمًا الأفضل للسيارة؟

اختبارات ناجحة لمحرك "VK-800" الروسي وتطويره لطائرة بايكال الخفيفة

رئيس إنفيديا: الذكاء الاصطناعي الصيني "محفز للتقدم العالمي"

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength