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

اخر الاخبار

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

ما الخدمات التي قدّمها موكب أشبال الطفّ لزائري عاشوراء؟

العتبة العباسية المقدسة تنظّم مسيرات عزائية لإحياء ذكرى عاشوراء في نينوى

قسم الشؤون الفكرية يحيي ذكرى استشهاد الإمام الحسين (عليه السلام) في القارة الإفريقية

قسمُ التربية والتعليم يقيم مجلسه العزائي السنوي بذكرى عاشوراء

المزيد

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

تناول الجبن.. مفيد للجسم أم خطر يهدد صحتك؟

طبيبة أسنان تحذر.. لا تتجاهل هذه العلامة بعد التنظيف

يجب أن تأكل المزيد من الشمام هذا الصيف.. إليك السبب ؟

تأثير صحي كبير.. كم بيضة يجب أن تتناول يوميا؟

المزيد

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

أداء خلايا البيروفسكايت الشمسية تحت الماء قد يزيد كفاءة تحويل الكهرباء

مسافة الأمان: أساس القيادة الآمنة وتجنب الحوادث

هل القيادة السريعة تعني استهلاك اكثر للوقود؟

لماذا يعتبر كوكب المريخ غير صالح للحياة؟

المزيد

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

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