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 
. For 
, the two possible sequences are 
and 
. And for 
, the four possible
sequences are 
, 
, 
, and 
(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 
and
three with 
.
Contact the MathWorld Team
Apollonian network