|
| |
|
|
A000571
|
|
Number of different scores that are possible in an n-team round-robin tournament.
(Formerly M1189 N0459)
|
|
13
| |
|
|
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; 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.
|
|
|
REFERENCES
| L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 123, Problem 21.
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).
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
| Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Index entries for sequences related to tournaments
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the x-rays of permutations
|
|
|
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.
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.
|
|
|
EXAMPLE
| a(3)=2, since either one node dominates [ 2,1,0 ] or each node defeats the next [ 1,1,1 ].
|
|
|
CROSSREFS
| Cf. A007747.
Sequence in context: A092920 A177377 A035053 * A077003 A046917 A187044
Adjacent sequences: A000568 A000569 A000570 * A000572 A000573 A000574
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| a(11) corrected by Kenneth Winston (Aug 05 1978). More terms from David W. Wilson (davidwwilson(AT)comcast.net).
|
| |
|
|
