login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000571 Number of different score sequences that are possible in an n-team round-robin 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 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.
Also number of score sequences of length n: weakly increasing sequences a[0,1,...,n-1] where sum(j=0..k, a[j]) >= k*(k+1)/2 and sum(j=0..n-1, a[j]) = (n+1)*n/2; see example. - Joerg Arndt, Mar 29 2014
REFERENCES
Dale H. Bent, Score problems of round-robin 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), 1-36. [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, 308-343.
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
Seiichi Manyama, Table of n, a(n) for n = 0..1675 (terms 0..100 from Sean A. Irvine)
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Dale H. Bent, Score problems of round-robin tournaments, Master's dissertation, Univ. Alberta, 1964. See Table 5 on page 52.
David E. Brown, Eric Culver, Bryce Frederickson, Sidney Tate, and Brent J. Thomas, Entropy of Tournament Digraphs, arXiv:1812.09458 [math.CO], 2018.
Anders Claesson, Mark Dukes, Atli Fannar Franklín, and Sigurður Örn Stefánsson, Counting tournament score sequences, arXiv:2209.03925 [math.CO], 2022.
Sebrina Ruth Cropper, Ranking Score Vectors of Tournaments (2011). All Graduate Reports and Creative Projects. Paper 91. Utah State University, School of Graduate Studies.
Jeong Han Kim and Boris Pittel, Confirming the Kleitman-Winston Conjecture on the Largest Coefficient in a q-Catalan Number, J. Comb. Theory Series A 92 (2000), 197-206.
P. A. MacMahon, An American tournament treated by the calculus of symmetric functions, Quart. J. Pure Appl. Math., 49 (1920), 1-36. Gives a(1) to a(9). [Annotated scanned copy, scanned at 300 dpi. Do not replace with a smaller file as the print is very tiny and hard to read.]
Yaakov Malinovsky and John W. Moon, On Round-Robin Tournaments with a Unique Maximum Score and Some Related Results, arXiv:2208.14932 [math.CO], 2022.
John W. Moon, Topics on tournaments, Holt, Rinehard and Winston (1968), see page 88.
T. V. Narayana and D. H. Bent, Computation of the number of score sequences in round-robin tournaments, Canad. Math. Bull., 7 (1964), 133-136 (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), 87-89. [The main result of this paper seems to be wrong - see A210726.] See also John Riordan, Erratum, J. Comb. Theory 6 (1969), 226.
Paul K. Stockmeyer, Counting Various Classes of Tournament Score Sequences, J. Integer Seq. 26 (2023), Article 23.5.2.
Eric Weisstein's World of Mathematics, Score Sequence.
Kenneth J. Winston and Daniel J. Kleitman, On the Asymptotic Number of Tournament Score Sequences, J. Comb. Theory Series A 35 (1983) 208-230.
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. - N. J. A. Sloane, May 06 2012
Logarithmic derivative yields A145855, the number of n-member subsets of 1..2n-1 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(n-k) for n>0 with a(0)=1. - Paul D. Hanna, Jul 17 2013
Comment from Paul K. Stockmeyer, Feb 18 2022 (Start)
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 Winston-Kleitman (1983). The final step was completed by Kim-Pittel (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 +...
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)
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] (* Jean-Franç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))}
{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
See A274098 for the most likely score sequence.
Sequence in context: A177377 A321994 A035053 * A077003 A210726 A046917
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
a(11) corrected by Kenneth Winston, Aug 05 1978
More terms from David W. Wilson
Thanks to Paul K. Stockmeyer for comments. - N. J. A. Sloane, Feb 18 2022
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 10:59 EST 2024. Contains 370378 sequences. (Running on oeis4.)