

A000571


Number of different scores that are possible in an nteam roundrobin tournament.
(Formerly M1189 N0459)


17



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, 7189259574618, 26295934251565, 96478910768821, 354998461378719, 1309755903513481
(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 outdegree; 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_{i1}) <= 1, p_i >= 0, i=1, ..., n.
Also number of score sequences of length n: weakly increasing sequences a[0,1,...,n1] where sum(j=0..k, a[j]) >= k*(k+1)/2 and sum(j=0..n1, a[j]) = (n1)*n/2; same as weak compositions of n*(n1) with partial sums up to position k at least k*(k+1)/2; see example.  Joerg Arndt, Mar 29 2014


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).
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 xrays of permutations
Sebrina Ruth Cropper, Ranking Score Vectors of Tournaments (2011). All Graduate Reports and Creative Projects. Paper 91. Utah State University, School of Graduate Studies.  From N. J. A. Sloane, Jun 10 2012
John W. Moon, Topics on tournaments, Holt, Rinehard and Winston (1968), see page 88.
T. V. Narayana and D. H. Best, Computation of the number of score sequences in roundrobin tournaments, Canad. Math. Bull., 7 (1964), 133136 (but table contains errors).
D. Recoskie and J. Sawada, The Taming of Two Alley CATs, 2012.
J. Riordan, The number of score sequences in tournaments, J. Combin. Theory, 5 (1968), 8789. [The main result of this paper seems to be wrong  see A210726.]
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 TE<C(n1, 2), =Sum_{k=0..E} f_{n1}(TE, k) else; then a(n)=Sum_{E=[n/2]..n1} f_n(C(n, 2), E), n >= 2.
Riordan seems to claim that a(n) = 2*a(n1)a(n2) + A046919(n), but this is not true.  N. J. A. Sloane, May 06 2012.
Logarithmic derivative yields A145855, the number of nmember subsets of 1..2n1 whose elements sum to a multiple of n.  Paul D. Hanna, Jul 17 2013
a(n) = (1/n) * Sum_{k=1..n} A145855(k) * a(nk) for n>0 with a(0)=1.  Paul D. Hanna, Jul 17 2013


EXAMPLE

a(3)=2, since either one node dominates [ 2,1,0 ] or each node defeats the next [ 1,1,1 ].
G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 22*x^6 + 59*x^7 + 167*x^8 +...
where the logarithm begins:
log(A(x)) = x + x^2/2 + 4*x^3/3 + 9*x^4/4 + 26*x^5/5 + 76*x^6/6 +...+ A145855(n)*x^n/n +...
From Joerg Arndt, Mar 29 2014: (Start)
The a(6) = 22 score sequences of length 6 are:
01: [ 0 1 2 3 4 5 ]
02: [ 0 1 2 4 4 4 ]
03: [ 0 1 3 3 3 5 ]
04: [ 0 1 3 3 4 4 ]
05: [ 0 2 2 2 4 5 ]
06: [ 0 2 2 3 3 5 ]
07: [ 0 2 2 3 4 4 ]
08: [ 0 2 3 3 3 4 ]
09: [ 0 3 3 3 3 3 ]
10: [ 1 1 1 3 4 5 ]
11: [ 1 1 1 4 4 4 ]
12: [ 1 1 2 2 4 5 ]
13: [ 1 1 2 3 3 5 ]
14: [ 1 1 2 3 4 4 ]
15: [ 1 1 3 3 3 4 ]
16: [ 1 2 2 2 3 5 ]
17: [ 1 2 2 2 4 4 ]
18: [ 1 2 2 3 3 4 ]
19: [ 1 2 3 3 3 3 ]
20: [ 2 2 2 2 2 5 ]
21: [ 2 2 2 2 3 4 ]
22: [ 2 2 2 3 3 3 ]
(End)


PROG

(PARI) {A145855(n)=sumdiv(n, d, (1)^(n+d)*eulerphi(n/d)*binomial(2*d, d)/(2*n))}
{a(n)=polcoeff(exp(sum(m=1, n, A145855(m)*x^m/m)+x*O(x^n)), n)} \\ Paul D. Hanna, Jul 17 2013


CROSSREFS

Cf. A007747, A210726, A145855.
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



