

A000571


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


22



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]) = (n+1)*n/2; see example.  Joerg Arndt, Mar 29 2014


REFERENCES

Dale H. Bent, Score problems of roundrobin tournaments, Master’s dissertation, Univ. Alberta, 1964. See Table 5 on page 52.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 123, Problem 21.
P. A. MacMahon, An American tournament treated by the calculus of symmetric functions, Quart. J. Pure Appl. Math., 49 (1920), 136. [Gives a[0)a(8).  N. J. A. Sloane, Jun 11 2016) Reproduced in Percy Alexander MacMahon Collected Papers, Volume I, George E. Andrews, ed., MIT Press, 1978, 308343.
J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 68.
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



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
There are constants c1, c2 such that
c_1*4^n/n^(5/2) < a(n) < c_2*4^n/n^(5/2).
Most of the proof appears in WinstonKleitman (1983). The final step was completed by KimPittel (2000). (End)
a(n) ~ c * 4^n / n^(5/2), where c = 0.3924780842992932228521178909875268946304664137141043398966808144665388...  Vaclav Kotesovec, Feb 21 2022


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 +...
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)


MATHEMATICA

max = 40; (* b = A145855 *) b[0] = 1; b[n_] := DivisorSum[n, (1)^(n+#)* EulerPhi[n/#]*Binomial[2*#, #]/(2*n)&]; s = Exp[Sum[b[m]*x^m/m, {m, 1, max}]] + O[x]^max; CoefficientList[s, x] (* JeanFrançois Alcover, Dec 06 2015, adapted from PARI *)


PROG

(PARI) {A145855(n)=sumdiv(n, d, (1)^(n+d)*eulerphi(n/d)*binomial(2*d, d)/(2*n))}


CROSSREFS

See A274098 for the most likely score sequence.


KEYWORD

nonn,nice


AUTHOR



EXTENSIONS

a(11) corrected by Kenneth Winston, Aug 05 1978


STATUS

approved



