|
%I M1189 N0459 #139 Mar 22 2024 12:33:51
%S 1,1,1,2,4,9,22,59,167,490,1486,4639,14805,48107,158808,531469,
%T 1799659,6157068,21258104,73996100,259451116,915695102,3251073303,
%U 11605141649,41631194766,150021775417,542875459724,1972050156181,7189259574618,26295934251565,96478910768821,354998461378719,1309755903513481
%N Number of different score sequences that are possible in an n-team round-robin tournament.
%C 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.
%C 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.
%C 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
%D Dale H. Bent, Score problems of round-robin tournaments, Master’s dissertation, Univ. Alberta, 1964. See Table 5 on page 52.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 123, Problem 21.
%D 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.
%D J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 68.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Seiichi Manyama, <a href="/A000571/b000571.txt">Table of n, a(n) for n = 0..1675</a> (terms 0..100 from Sean A. Irvine)
%H C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, <a href="https://arxiv.org/abs/math/0506334">On the X-rays of permutations</a>, arXiv:math/0506334 [math.CO], 2005.
%H Dale H. Bent, <a href="https://archive.org/details/scoreproblemsofr00dale">Score problems of round-robin tournaments</a>, Master's dissertation, Univ. Alberta, 1964. See Table 5 on page 52.
%H David E. Brown, Eric Culver, Bryce Frederickson, Sidney Tate, and Brent J. Thomas, <a href="https://arxiv.org/abs/1812.09458">Entropy of Tournament Digraphs</a>, arXiv:1812.09458 [math.CO], 2018.
%H Anders Claesson, Mark Dukes, Atli Fannar Franklín, and Sigurður Örn Stefánsson, <a href="https://arxiv.org/abs/2209.03925">Counting tournament score sequences</a>, arXiv:2209.03925 [math.CO], 2022.
%H Sebrina Ruth Cropper, <a href="http://digitalcommons.usu.edu/gradreports/91">Ranking Score Vectors of Tournaments</a> (2011). All Graduate Reports and Creative Projects. Paper 91. Utah State University, School of Graduate Studies.
%H Serte Donderwinkel and Brett Kolesnik, <a href="https://arxiv.org/abs/2403.12940">Tournaments and random walks</a>, arXiv:2403.12940 [math.PR], 2024. See index, p. 34.
%H Jeong Han Kim and Boris Pittel, <a href="https://doi.org/10.1006/jcta.1999.3054">Confirming the Kleitman-Winston Conjecture on the Largest Coefficient in a q-Catalan Number</a>, J. Comb. Theory Series A 92 (2000), 197-206.
%H P. A. MacMahon, <a href="/A274098/a274098.pdf">An American tournament treated by the calculus of symmetric functions</a>, 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.]
%H Yaakov Malinovsky and John W. Moon, <a href="https://arxiv.org/abs/2208.14932">On Round-Robin Tournaments with a Unique Maximum Score and Some Related Results</a>, arXiv:2208.14932 [math.CO], 2022.
%H John W. Moon, <a href="http://www.gutenberg.org/ebooks/42833">Topics on tournaments</a>, Holt, Rinehard and Winston (1968), see page 88.
%H T. V. Narayana and D. H. Bent, <a href="http://dx.doi.org/10.4153/CMB-1964-015-1">Computation of the number of score sequences in round-robin tournaments</a>, Canad. Math. Bull., 7 (1964), 133-136 (but table contains errors).
%H D. Recoskie and J. Sawada, <a href="http://www.socs.uoguelph.ca/~sawada/papers/alley.pdf">The Taming of Two Alley CATs</a>, 2012.
%H J. Riordan, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80032-8">The number of score sequences in tournaments</a>, 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.
%H Paul K. Stockmeyer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Stockmeyer/stock14.html">Counting Various Classes of Tournament Score Sequences</a>, J. Integer Seq. 26 (2023), Article 23.5.2.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ScoreSequence.html">Score Sequence.</a>
%H K. Winston, <a href="/A000571/a000571.pdf">Letter to N. J. A. Sloane, Aug 05 1978</a>
%H Kenneth J. Winston and Daniel J. Kleitman, <a href="https://doi.org/10.1016/0097-3165(83)90008-0">On the Asymptotic Number of Tournament Score Sequences</a>, J. Comb. Theory Series A 35 (1983) 208-230.
%H <a href="/index/To#tournament">Index entries for sequences related to tournaments</a>
%F 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.
%F 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
%F 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
%F 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
%F Comment from _Paul K. Stockmeyer_, Feb 18 2022 (Start)
%F There are constants c1, c2 such that
%F c_1*4^n/n^(5/2) < a(n) < c_2*4^n/n^(5/2).
%F Most of the proof appears in Winston-Kleitman (1983). The final step was completed by Kim-Pittel (2000). (End)
%F a(n) ~ c * 4^n / n^(5/2), where c = 0.3924780842992932228521178909875268946304664137141043398966808144665388... - _Vaclav Kotesovec_, Feb 21 2022
%e a(3)=2, since either one node dominates [ 2,1,0 ] or each node defeats the next [ 1,1,1 ].
%e 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 +...
%e where the logarithm begins:
%e 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 +...
%e From _Joerg Arndt_, Mar 29 2014: (Start)
%e The a(6) = 22 score sequences of length 6 are:
%e 01: [ 0 1 2 3 4 5 ]
%e 02: [ 0 1 2 4 4 4 ]
%e 03: [ 0 1 3 3 3 5 ]
%e 04: [ 0 1 3 3 4 4 ]
%e 05: [ 0 2 2 2 4 5 ]
%e 06: [ 0 2 2 3 3 5 ]
%e 07: [ 0 2 2 3 4 4 ]
%e 08: [ 0 2 3 3 3 4 ]
%e 09: [ 0 3 3 3 3 3 ]
%e 10: [ 1 1 1 3 4 5 ]
%e 11: [ 1 1 1 4 4 4 ]
%e 12: [ 1 1 2 2 4 5 ]
%e 13: [ 1 1 2 3 3 5 ]
%e 14: [ 1 1 2 3 4 4 ]
%e 15: [ 1 1 3 3 3 4 ]
%e 16: [ 1 2 2 2 3 5 ]
%e 17: [ 1 2 2 2 4 4 ]
%e 18: [ 1 2 2 3 3 4 ]
%e 19: [ 1 2 3 3 3 3 ]
%e 20: [ 2 2 2 2 2 5 ]
%e 21: [ 2 2 2 2 3 4 ]
%e 22: [ 2 2 2 3 3 3 ]
%e (End)
%t 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 *)
%o (PARI) {A145855(n)=sumdiv(n,d, (-1)^(n+d)*eulerphi(n/d)*binomial(2*d,d)/(2*n))}
%o {a(n)=polcoeff(exp(sum(m=1,n,A145855(m)*x^m/m)+x*O(x^n)),n)} \\ _Paul D. Hanna_, Jul 17 2013
%Y Cf. A007747, A210726, A145855.
%Y See A274098 for the most likely score sequence.
%K nonn,nice
%O 0,4
%A _N. J. A. Sloane_
%E a(11) corrected by Kenneth Winston, Aug 05 1978
%E More terms from _David W. Wilson_
%E Thanks to _Paul K. Stockmeyer_ for comments. - _N. J. A. Sloane_, Feb 18 2022
|
