主题
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-锦标赛。

另请参阅

有向图, 定向图, 出度, 锦标赛, 竞赛图矩阵

使用 Wolfram|Alpha 探索

参考文献

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

在 Wolfram|Alpha 中被引用

得分序列

请引用为

Weisstein, Eric W. "得分序列。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/ScoreSequence.html

主题分类