A000571 Number of different score sequences that are possible in an n-team round-robin tournament. (Formerly M1189 N0459)

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

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.

Serte Donderwinkel and Brett Kolesnik, Tournaments and random walks, arXiv:2403.12940 [math.PR], 2024. See index, p. 34.

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.

K. Winston, Letter to N. J. A. Sloane, Aug 05 1978

Kenneth J. Winston and Daniel J. Kleitman, On the Asymptotic Number of Tournament Score Sequences, J. Comb. Theory Series A 35 (1983) 208-230.

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 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

Cf. A007747, A210726, A145855.

See A274098 for the most likely score sequence.

Sequence in context: A177377 A321994 A035053 * A077003 A210726 A046917

Adjacent sequences: A000568 A000569 A000570 * A000572 A000573 A000574

Keyword

nonn,nice

Author

N. J. A. Sloane

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