|
| |
|
|
A000571
|
|
Number of different scores that are possible in an n-team round-robin tournament.
(Formerly M1189 N0459)
|
|
16
|
|
|
|
1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, 158808, 531469, 1799659, 6157068, 21258104, 73996100, 259451116, 915695102, 3251073303, 11605141649, 41631194766, 150021775417, 542875459724, 1972050156181
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
A tournament is a complete graph with one arrow on each edge; the score of a node is its out-degree; a(n) is number of different score sequences when there are n nodes.
Also number of nonnegative integer points (p_1, p_2, ..., p_n) in polytope p_0=p_{n+1}=0, 2p_i -(p_{i+1}+p_{i-1}) <= 1, p_i >= 0, i=1, ..., n.
|
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 123, Problem 21.
Cropper, Sebrina Ruth, "Ranking Score Vectors of Tournaments" (2011). All Graduate Reports and Creative Projects. Paper 91. Utah State University, School of Graduate Studies, http://digitalcommons.usu.edu/gradreports/91. - From N. J. A. Sloane, Jun 10 2012
J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 68 (but table contains errors).
T. V. Narayana and D. H. Best, Computation of the number of score sequences in round-robin tournaments, Canad. Math. Bull., 7 (1964), 133-136 (but table contains errors).
J. Riordan, The number of score sequences in tournaments, J. Combin. Theory, 5 (1968), 87-89. [The main result of this paper seems to be wrong - see A210726.]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Sean A. Irvine, Table of n, a(n) for n = 0..100
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the x-rays of permutations
D. Recoskie and J. Sawada, The Taming of Two Alley CATs, 2012.
Eric Weisstein's World of Mathematics, Score Sequence.
Index entries for sequences related to tournaments
|
|
|
FORMULA
|
Let f_1(T, E)=1 if T=E>=0, =0 else; f_n(T, E)=0 if T-E<C(n-1, 2), =Sum_{k=0..E} f_{n-1}(T-E, k) else; then a(n)=Sum_{E=[n/2]..n-1} f_n(C(n, 2), E), n >= 2.
Riordan seems to claim that a(n) = 2*a(n-1)-a(n-2) + A046919(n), but this is not true. - From N. J. A. Sloane, May 06 2012.
|
|
|
EXAMPLE
|
a(3)=2, since either one node dominates [ 2,1,0 ] or each node defeats the next [ 1,1,1 ].
|
|
|
CROSSREFS
|
Cf. A007747, A210726.
Sequence in context: A092920 A177377 A035053 * A077003 A210726 A046917
Adjacent sequences: A000568 A000569 A000570 * A000572 A000573 A000574
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
a(11) corrected by Kenneth Winston (Aug 05 1978). More terms from David W. Wilson.
|
|
|
STATUS
|
approved
|
| |
|
|
