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

اخر الاخبار

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

قسم الشؤون الدينية يوزع أكثر من ألفي وجبة طعام للمعزين في ذكرى عاشوراء بنينوى

قسم الشؤون الطبية يواصل تقديم خدماته الصحية لزائري عاشوراء

جموع المعزين تحيي مراسم يوم العاشر من شهر المحرم عند المرقدين الطاهرين

قسم العلاقات يطلق محطات فتية الكفيل الثقافية في محافظة نينوى

المزيد

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

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

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

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

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

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