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