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

اخر الاخبار

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

قسم الشؤون الفكرية يقيم أمسيات قرآنية في غانا ونيجيريا ضمن برنامج سفرة الكفيل الرمضانية

شعبة التوجيه الديني النسوي تختتم محافلها القرآنية الرمضانية

المجمع العلمي يختتم مسابقة رحيق الولاء ضمن فعاليات ملتقى النورين الخامس في بابل

الحلقة 27 من جائزة العميد القرآنية تشهد مشاركة 5 قرّاء من فئة الكبار ضمن المرحلة النهائية

المزيد

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

كوب قبل النوم.. مشروب طبيعي يحارب الأرق

دون أدوية.. طريقة طبيعية لخفض ضغط الدم بفعالية مذهلة

المعكرونة ليست عدوك.. كيف تصبح جزءا من وجبة صحية متوازنة؟

دراسة: تناول القهوة يوميا يخفض خطر الإصابة بالاضطرابات النفسية

المزيد

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

علماء روس يخططون لبناء منشأة للكشف عن المادة المظلمة

ثاني أكسيد الكربون ليس تهديدا للمناخ فقط.. بل لصحة الإنسان أيضا!

ديدان الأرض تكشف تلوث التربة بالمعادن الثقيلة

خبير أرصاد جوية: ظاهرة النينيو القادمة قد تكون الأقوى خلال 10 سنوات

المزيد

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

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