A000571 -id:A000571 - cp's OEIS frontend

A068029 Table of sorted score sequences (including duplications), with A000571 giving the number of score sequences of length n.

0, 0, 1, 0, 1, 2, 1, 1, 1, 0, 1, 2, 3, 0, 2, 2, 2, 1, 1, 1, 3, 1, 1, 2, 2, 0, 1, 2, 3, 4, 0, 1, 3, 3, 3, 0, 2, 2, 2, 4, 0, 2, 2, 3, 3, 1, 1, 1, 3, 4, 1, 1, 2, 2, 4, 1, 1, 2, 3, 3, 1, 2, 2, 2, 3, 2, 2, 2, 2, 2, 0, 1, 2, 3, 4, 5, 0, 1, 2, 4, 4, 4, 0, 1, 3, 3, 3, 5, 0, 1, 3, 3, 4, 4, 0, 2, 2, 2, 4, 5, 0, 2

Offset: 1

Eric W. Weisstein, Feb 10 2002

			{0} is the score sequence of length 1.
{0,1} is the score sequence of length 2.
{0,1,2} and {1,1,1} are the two score sequences of length 3.

Sean A. Irvine, Java program (github)
D. Recoskie and J. Sawada, The Taming of Two Alley CATs, 2012.
Eric Weisstein's World of Mathematics, Score Sequence

Cf. A000571.

A046917 Erroneous version of A000571.

Original entry on oeis.org

1, 1, 2, 4, 9, 22, 59, 169, 506, 1586

Offset: 1

dead

A007747 Number of nonnegative integer points (p_1,p_2,...,p_n) in polytope defined by p_0 = p_{n+1} = 0, 2p_i - (p_{i+1} + p_{i-1}) <= 2, p_i >= 0, i=1,...,n. Number of score sequences in a chess tournament with n+1 players (with 3 outcomes for each game).

Original entry on oeis.org

1, 2, 5, 16, 59, 247, 1111, 5302, 26376, 135670, 716542, 3868142, 21265884, 118741369, 671906876, 3846342253, 22243294360, 129793088770, 763444949789, 4522896682789, 26968749517543, 161750625450884

Offset: 0

P. Di Francesco (philippe(AT)amoco.saclay.cea.fr), N. J. A. Sloane

A correspondence between the points in the polytope and the chess scores was found by Svante Linusson (linusson(AT)matematik.su.se):

The score sequences are partitions (a_1,...,a_n) of 2C(n,2) of length <= n that are majorized by 2n,2n-2,2n-4,...,2,0; i.e. f(n,k) := 2n+2n-2+...+(2n-2k+2)-(a_1+a_2+...+a_k) >= 0 for all k. The sequence 0=f(n,0),f(n,1),f(n,2),...,f(n,n)=0 is in the polytope. This establishes the bijection.

			With 3 players the possible scores sequences are {{0,2,4}, {0,3,3}, {1,1,4}, {1,2,3}, {2,2,2}}.
With 4 players they are {{0,2,4,6}, {0,2,5,5}, {0,3,3,6}, {0,3,4,5}, {0,4,4,4}, {1,1,4,6}, {1,1,5,5}, {1,2,3,6}, {1,2,4,5}, {1,3,3,5}, {1,3,4,4}, {2,2,2,6}, {2,2,3,5}, {2,2,4,4}, {2,3,3,4}, {3,3,3,3}}.

P. A. MacMahon, Chess tournaments and the like treated by the calculus of symmetric functions, Coll. Papers I, MIT Press, 344-375.

Qihao Ye, Table of n, a(n) for n = 0..1214 (terms 0..39 from Jon E. Schoenfield)
P. Di Francesco, M. Gaudin, C. Itzykson and F. Lesage, Laughlin's wave functions, Coulomb gases and expansions of the discriminant, Int. J. Mod. Phys. A9 (1994) 4257.
Jon E. Schoenfield, Comments on this sequence
Index entries for sequences related to tournaments

Cf. A000571, A047730, A064626, A064422.

f[K_, L_, S_, X_] /; K > 1 && L <= S/K <= X + 1 - K := f[K, L, S, X] = Sum[f[K - 1, i, S - i, X], {i, L, Floor[S/K]}]; f[1, L_, S_, X_] /; L <= S <= X = 1; f[, , , ] = 0; a[n_] := f[n + 1, 0, n*(n + 1), 2*n]; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Jul 13 2012, after Jon E. Schoenfield *)

Schoenfield (see Comments link) gives a recursive method for computing this sequence.

More terms from David W. Wilson

A047730 Number of score sequences in tournament with n players, when 4 points are awarded in each game.

Original entry on oeis.org

1, 3, 13, 76, 521, 3996, 32923, 286202, 2590347, 24203935, 232050202, 2272449745, 22653570386, 229274897514, 2350933487206, 24381053759852, 255382755251622, 2698732882975782, 28743579211912338

Offset: 1

David W. Wilson

nonn

P. A. MacMahon, Chess tournaments and the like treated by the calculus o symmetric functions, Coll. Papers I, MIT Press, 344-375.

Cf. A000571, A007747, A047729, A064626, A064422.

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}) <= 4, p_i >= 0, i=1, ..., n.

A047729 Number of score sequences in tournament with n players, when 3 points are awarded in each game.

Original entry on oeis.org

1, 2, 8, 37, 198, 1178, 7548, 50944, 357855, 2595250, 19313372, 146815503, 1136158495, 8927025989, 71065654235, 572215412354, 4653746621835, 38184724333615, 315792633485360, 2630183440412617, 22046522161472304

Offset: 1

David W. Wilson

nonn

P. A. MacMahon, Chess tournaments and the like treated by the calculus of symmetric functions, Coll. Papers I, MIT Press, 344-375.

Qihao Ye, Table of n, a(n) for n = 1..1032
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Index entries for sequences related to tournaments

Cf. A000571, A007747.

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}) <= 3, p_i >= 0, i=1, ..., n.

A047731 Number of score sequences in tournament with n players, when 5 points are awarded in each game.

Original entry on oeis.org

1, 3, 18, 131, 1111, 10461, 105819, 1127413, 12499673, 143021541, 1678718575, 20123155604, 245521479531, 3041006378312, 38157059717410, 484209044329613, 6205758830280388, 80235572611152385

Offset: 1

David W. Wilson

nonn

P. A. MacMahon, Chess tournaments and the like treated by the calculus o symmetric functions, Coll. Papers I, MIT Press, 344-375.

Cf. A000571, A007747, A047729, A047730.

A145855 Number of n-element subsets of {1,2,...,2n-1} whose elements sum to a multiple of n.

Original entry on oeis.org

1, 1, 4, 9, 26, 76, 246, 809, 2704, 9226, 32066, 112716, 400024, 1432614, 5170604, 18784169, 68635478, 252085792, 930138522, 3446167834, 12815663844, 47820414962, 178987624514, 671825133644, 2528212128776, 9536894664376

Offset: 1

T. D. Noe, Oct 21 2008, Oct 22 2008, Oct 24 2008

nonn

It is easy to see that {1,2,...,2n-1} can be replaced by any 2n-1 consecutive numbers and the results will be the same. Erdos, Ginzburg and Ziv proved that every set of 2n-1 numbers -- not necessarily consecutive -- contains a subset of n elements whose sum is a multiple of n.

			a(3)=4 because, of the 10 3-element subsets of 1..7, only {1,2,3}, {1,3,5}, {2,3,4} and {3,4,5} have sums that are multiples of 3.
L.g.f.: L(x) = x + x^2/2 + 4*x^3/3 + 9*x^4/4 + 26*x^5/5 + 76*x^6/6 + 246*x^7/7 +...
where exponentiation yields the g.f. of A000571:
exp(L(x)) = 1 + x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 22*x^6 + 59*x^7 + 167*x^8 +...

Seiichi Manyama, Table of n, a(n) for n = 1..1669 (terms 1..200 from T. D. Noe)
Max Alekseyev, Proof of Jovovic's formula, 2008.
Michal Bassan, Serte Donderwinkel, and Brett Kolesnik, Tournament score sequences, Erdős-Ginzburg-Ziv numbers, and the Lévy-Khintchine method, arXiv:2407.01441 [math.CO], 2024. See p. 7.
Shane Chern, An extension of a formula of Jovovic, Integers (2019) Vol. 19, Article A47.
Anders Claesson, Mark Dukes, Atli Fannar Franklín, and Sigurður Örn Stefánsson, Counting tournament score sequences, arXiv:2209.03925 [math.CO], 2022.
P. Erdős, A. Ginzburg and A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel 10 (1961).
Steven Rayan, Aspects of the topology and combinatorics of Higgs bundle moduli spaces, arXiv:1809.05732 [math.AG], 2018.
Mithat Ünsal, Graded Hilbert spaces, quantum distillation and connecting SQCD to QCD, arXiv:2104.12352 [hep-th], 2021.

Cf. A000571, A227532.

Column k=2 of A309148.

Table[Length[Select[Plus@@@Subsets[Range[2n-1],{n}], Mod[ #,n]==0&]], {n,10}]
Table[d=Divisors[n]; Sum[(-1)^(n+d[[i]]) EulerPhi[n/d[[i]]] Binomial[2d[[i]], d[[i]]]/2/n, {i,Length[d]}], {n,30}] (* T. D. Noe, Oct 24 2008 *)

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

{A227532(n, k)=local(G=1); for(i=1, n, G=1+x*subst(G, x, q*x)*G +x*O(x^n)); n*polcoeff(polcoeff(log(G), n, x), k, q)}
{a(n)=sum(k=0,n\2, A227532(n, n*k))} \\ Paul D. Hanna, Jul 17 2013

a(n) = (1/(2*n))*Sum_{d|n} (-1)^(n+d)*phi(n/d)*binomial(2*d,d). Conjectured by Vladeta Jovovic, Oct 22 2008; proved by Max Alekseyev, Oct 23 2008 (see link).
a(2n+1) = A003239(2n+1) and a(2n) = A003239(2n) - A003239(d), where d is the largest odd divisor of n. - T. D. Noe, Oct 24 2008
a(n) = Sum_{d|n} (-1)^(n+d)*d*A131868(d). - Vladeta Jovovic, Oct 28 2008
a(n) = Sum_{k=0..[n/2]} A227532(n,n*k), where A227532 is the logarithmic derivative, wrt x, of the g.f. G(x,q) = 1 + x*G(q*x,q)*G(x,q) of triangle A227543. - Paul D. Hanna, Jul 17 2013
Logarithmic derivative of A000571, the number of different scores that are possible in an n-team round-robin tournament. - Paul D. Hanna, Jul 17 2013
G.f.: -Sum_{m >= 1} (phi(m)/m) * log((1 + sqrt(1 + 4*(-y)^m))/2). - Petros Hadjicostas, Jul 15 2019
a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 28 2023

Extension T. D. Noe, Oct 24 2008

A046919 Maximal coefficient of polynomial p(n), with p(3)=1, p(n) = (1 - t^(2n - 4))(1 - t^(2n - 3))p(n - 1)/((1 - t^(n - 3))*(1 - t^n)).

Original entry on oeis.org

1, 1, 3, 8, 24, 73, 227, 734, 2430, 8150, 27718, 95514, 332578, 1168261, 4136477, 14749992, 52925886, 190973410, 692583902, 2523265494, 9231352260, 33901898722, 124940568222, 461938289518, 1713007181342, 6369928427268, 23747917426918, 88747514693530, 332397792962692, 1247582980566935, 4691740496135919, 17676678143316236, 66714895880626460, 252207367615436780

Offset: 3

N. J. A. Sloane

a(n) is also the number of partitions of n(n-1)/2 into n (nonzero) parts, none greater than n-2 [Riordan].

			1; 1+t+t^2+t^3+t^4+t^5, t^10+t^9+2*t^8+2*t^7+3*t^6+3*t^5+3*t^4+2*t^3+2*t^2+t+1, ...

Vaclav Kotesovec, Table of n, a(n) for n = 3..200 (terms 3..50 from N. J. A. Sloane)
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 - compare A000571 and A210726.]

Cf. A000571, A046918, A210726.

p := proc(n)
option remember;
if n = 3 then 1 else
simplify((1-t^(2*n-4))*(1-t^(2*n-3))*p(n-1)/((1-t^(n-3))*(1-t^n)));
fi; end;
for i from 3 to 40 do
lprint(coeff(expand(p(i)),t,i*(i-3)/2)):
od:

p[3] = 1; p[n_] := p[n] = (1 - t^(2*n-4))*(1 - t^(2*n-3))*(p[n-1]/((1 - t^(n-3))*(1 - t^n)))// Simplify // Expand; a[n_] := Coefficient[p[n], t, n*(n-3)/2]; Table[a[n], {n, 3, 40}] (* Jean-François Alcover, Aug 01 2013, after Maple *)

a(n) ~ sqrt(3) * 2^(2*n-3) / (Pi * n^2). - Vaclav Kotesovec, Jan 07 2023

Corrected terms and Maple program. - N. J. A. Sloane, May 09 2012

A125032 Triangle read by rows: T(n,k) = number of tournaments with n players which have the k-th score sequence. The score sequences are in the same order as A068029 and start with the empty score sequence.

Original entry on oeis.org

1, 1, 2, 6, 2, 24, 8, 8, 24, 120, 40, 40, 120, 40, 120, 240, 280, 24, 720, 240, 240, 720, 240, 720, 1440, 1680, 144, 240, 80, 720, 1440, 2880, 1680, 1680, 1680, 8640, 2400, 144, 2400, 2640, 5040, 1680, 1680, 5040, 1680, 5040, 10080, 11760, 1008, 1680, 560

Offset: 1

Martin Fuller, Nov 16 2006

The score sequences are sorted by number of players and then lexicographically.

There are A000571(m) score sequences for m players. The sum of all the a(n) for m players is A006125(m)=2^(m(m-1)/2).

			There are two score sequences with 3 players: [0,1,2] from 6 tournaments and [1,1,1] from 2 tournaments. These score sequences come 4th and 5th respectively, so a(4)=6 and a(5)=2.

Martin Fuller, Table of n, a(n) for n = 1..2242
Eric Weisstein's World of Mathematics, Score Sequence
Index entries for sequences related to tournaments

Cf. A000571, A006125, A068029, A125031 (number of highest scorers), A123553.

Other sequences that can be calculated using this one: A013976, A125031.

A210726 a(2)=1, a(3)=2; thereafter a(n) = 2a(n-1)-a(n-2)+A046919(n).

Original entry on oeis.org

1, 2, 4, 9, 22, 59, 169, 506, 1577, 5078, 16729, 56098, 190981, 658442, 2294164, 8066363, 28588554, 102036631, 366458118, 1323463507, 4803734390, 17515357533, 64128879398, 235682969485, 869175349090, 3215674910037, 11932102898252, 44396448313385, 165608308422048, 619217961493403, 2320410595131693, 8713343724905902, 32782954997996347, 123567462151713252, 466559336920866937, 1764469819249171154

Offset: 2

N. J. A. Sloane, May 09 2012

nonn

According to Riordan (1968), this is the number of possible score sequences in a tournament with n nodes, but the latter is given by A000571, which is a different sequence.

J. Riordan, The number of score sequences in tournaments, J. Combin. Theory, 5 (1968), 87-89.

Cf. A046919.

cp's OEIS Frontend

A068029 Table of sorted score sequences (including duplications), with A000571 giving the number of score sequences of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

A046917 Erroneous version of A000571.

Views

Author

Keywords

A007747 Number of nonnegative integer points (p_1,p_2,...,p_n) in polytope defined by p_0 = p_{n+1} = 0, 2p_i - (p_{i+1} + p_{i-1}) <= 2, p_i >= 0, i=1,...,n. Number of score sequences in a chess tournament with n+1 players (with 3 outcomes for each game).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A047730 Number of score sequences in tournament with n players, when 4 points are awarded in each game.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A047729 Number of score sequences in tournament with n players, when 3 points are awarded in each game.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A047731 Number of score sequences in tournament with n players, when 5 points are awarded in each game.

Views

Author

Keywords

References

Links

Crossrefs

A145855 Number of n-element subsets of {1,2,...,2n-1} whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A046919 Maximal coefficient of polynomial p(n), with p(3)=1, p(n) = (1 - t^(2*n - 4))*(1 - t^(2*n - 3))*p(n - 1)/((1 - t^(n - 3))*(1 - t^n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A125032 Triangle read by rows: T(n,k) = number of tournaments with n players which have the k-th score sequence. The score sequences are in the same order as A068029 and start with the empty score sequence.

Views

Author

Keywords

Comments

A046919 Maximal coefficient of polynomial p(n), with p(3)=1, p(n) = (1 - t^(2n - 4))(1 - t^(2n - 3))p(n - 1)/((1 - t^(n - 3))*(1 - t^n)).