主題
Search

得分序列

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook
ScoreSequence

競賽圖的得分序列是相應競賽圖的圖頂點的出度的單調非遞減序列。因此，長度為 n 的得分序列的元素介於 0 和 n-1 之間（包括 0 和 n-1）。得分序列之所以如此命名，是因為它們對應於在一場錦標賽中，由 n 名玩家組成的小組的成員可能獲得的分數集合，其中每位玩家與其他 n-1 位玩家進行比賽，並且每場比賽的結果都是一名玩家獲勝，另一名玩家失敗。（給定錦標賽的得分序列是從按非遞減順序排列的出度集合中獲得的，因此總和必須為 (n; 2)，其中 (n; 2) 是二項式係數。）

例如，n=2 時唯一可能的得分序列是 {0,1}。對於 n=3，兩種可能的序列是 {0,1,2} 和 {1,1,1}。對於 n=4，四種可能的序列是 {0,1,2,3}、{0,2,2,2}、{1,1,1,3} 和 {1,1,2,2} (OEIS A068029)。

Landau (1953) 證明了整數序列 s_1<=s_2<=s_3<=...<=s_n (0<=s_i<=n-1) 是得分序列當且僅當

sum_(i=1)^ks_i>=(k; 2)

對於 k=1, ..., n-1，其中 (k; 2) 是二項式係數，並且等式成立條件為

sum_(i=1)^ns_i=(n; 2)

(Harary 1994, p. 211, Ruskey)。

對於 n=1, 2, ...，不同得分序列的數量分別為 1, 1, 2, 4, 9, 22, 59, 167, ... (OEIS A000571)。一個得分序列不能唯一確定一個錦標賽，例如，存在兩個得分序列為 {1,1,2,3,3} 的 4-錦標賽和三個得分序列為 {1,2,2,2,3} 的 4-錦標賽。

另請參閱

有向圖, 定向圖, 出度, 錦標賽, 競賽圖矩陣

使用 探索

參考文獻

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

在 中被引用

得分序列

請引用為

Weisstein, Eric W. "得分序列。" 來自 —— 資源。 https://mathworld.tw/ScoreSequence.html

主題分類