A145855 -id:A145855 - cp's OEIS frontend

A000571 Number of different score sequences that are possible in an n-team round-robin tournament.

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

N. J. A. Sloane

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

			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)

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

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

Cf. A007747, A210726, A145855.

See A274098 for the most likely score sequence.

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

{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

Let f_1(T, E)=1 if T=E>=0, =0 else; f_n(T, E)=0 if T-E= 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

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

A309148 A(n,k) is (1/k) times the number of n-member subsets of [k*n] whose elements sum to a multiple of n; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 2, 4, 0, 1, 3, 10, 9, 1, 1, 4, 19, 42, 26, 0, 1, 5, 31, 115, 201, 76, 1, 1, 6, 46, 244, 776, 1028, 246, 0, 1, 7, 64, 445, 2126, 5601, 5538, 809, 1, 1, 8, 85, 734, 4751, 19780, 42288, 30666, 2704, 0, 1, 9, 109, 1127, 9276, 54086, 192130, 328755, 173593, 9226, 1

Offset: 1

Alois P. Heinz, Jul 14 2019

For k > 1 also (1/(k-1)) times the number of n-member subsets of [k*n-1] whose elements sum to a multiple of n.

The sequence of row n satisfies a linear recurrence with constant coefficients of order n.

			Square array A(n,k) begins:
  1,   1,    1,     1,      1,      1,       1, ...
  0,   1,    2,     3,      4,      5,       6, ...
  1,   4,   10,    19,     31,     46,      64, ...
  0,   9,   42,   115,    244,    445,     734, ...
  1,  26,  201,   776,   2126,   4751,    9276, ...
  0,  76, 1028,  5601,  19780,  54086,  124872, ...
  1, 246, 5538, 42288, 192130, 642342, 1753074, ...

Alois P. Heinz, Rows n = 1..150, flattened

Columns k=1-10 give: A000035, A145855, A309182, A309183, A309184, A309185, A309186, A309187, A309188, A309189.
Rows n=1-3 give: A000012, A001477(k-1), A005448.
Main diagonal gives A308667.
Cf. A000010, A304482.

with(numtheory):
A:= (n, k)-> add(binomial(k*d, d)*(-1)^(n+d)*
             phi(n/d), d in divisors(n))/(n*k):
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);

A[n_, k_] := 1/(n k) Sum[Binomial[k d, d] (-1)^(n+d) EulerPhi[n/d], {d, Divisors[n]}];
Table[A[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 04 2019 *)

A(n,k) = 1/(n*k) * Sum_{d|n} binomial(k*d,d)*(-1)^(n+d)*phi(n/d).

A(n,k) = (1/k) * A304482(n,k).

A169888 Number of n-member subsets of 1..2n whose elements sum to a multiple of n.

Original entry on oeis.org

1, 2, 2, 8, 18, 52, 152, 492, 1618, 5408, 18452, 64132, 225432, 800048, 2865228, 10341208, 37568338, 137270956, 504171584, 1860277044, 6892335668, 25631327688, 95640829924, 357975249028, 1343650267288, 5056424257552, 19073789328752, 72108867620204

Offset: 0

N. J. A. Sloane, Jul 07 2010, based on a letter from Jean-Claude Babois

nonn

This is twice A145855 (for n>0), which is the main entry for this problem.

Alois P. Heinz, Table of n, a(n) for n = 0..1669

Cf. A061865, A119358, A145855, A318431, A318432, A318433.

Column k=2 of A304482.

with(combinat): t0:=[]; for n from 1 to 8 do ans:=0; t1:=choose(2*n,n); for i in t1 do s1:=add(i[j],j=1..n); if s1 mod n = 0 then ans:=ans+1; fi; od: t0:=[op(t0),ans]; od:

a[n_] := Sum[(-1)^(n+d)*EulerPhi[n/d]*Binomial[2d, d]/n, {d, Divisors[n]}]; Table[a[n], {n, 1, 26}] (* Jean-François Alcover, Oct 22 2012, after T. D. Noe's program in A145855 *)

a(n) = if(n==0, 1, sumdiv(n, d, (-1)^(n+d)*eulerphi(n/d)*binomial(2*d, d)/n)); \\ Altug Alkan, Aug 27 2018, after T. D. Noe at A145855

a(n) = A061865(2n,n). - Alois P. Heinz, Aug 28 2018

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

a(0)=1 prepended by Alois P. Heinz, Aug 26 2018

A131868 a(n) = (2n^2)^(-1)Sum_{d|n} (-1)^(n+d)moebius(n/d)binomial(2*d,d).

Original entry on oeis.org

1, 1, 1, 2, 5, 13, 35, 100, 300, 925, 2915, 9386, 30771, 102347, 344705, 1173960, 4037381, 14004912, 48954659, 172307930, 610269695, 2173656683, 7782070631, 27992709172, 101128485150, 366803656323, 1335349400274, 4877991428982

Offset: 1

Vladeta Jovovic, Oct 04 2007

n*a(n) is the number of n-member subsets of {1,2,3,...,2*n-1} that sum to 1 mod n, cf. A145855. - Vladeta Jovovic, Oct 28 2008

a(n) is the number of orbits under the S_n action on a set closely related to the set of parking functions. See Konvalinka-Tewari reference below. - Vasu Tewari, Mar 17 2020

G. C. Greubel, Table of n, a(n) for n = 1..1000
Kunal Gupta and Pietro Longhi, Vortices on Cylinders and Warped Exponential Networks, arXiv:2407.08445 [hep-th], 2024. See pp. 41, 49.
M. Kontsevich, R. Stanley, O. Gorodetsky, et al. A congruence involving binomial coefficients, Mathoverflow, 2015.
Matjaž Konvalinka and Vasu Tewari, Some natural extensions of the parking space, arXiv:2003.04134 [math.CO], 2020.
Jerome Malenfant, On the Matrix-Element Expansion of a Circulant Determinant, arXiv:1502.06012 [math.NT], 2015.
Steven Rayan, Aspects of the topology and combinatorics of Higgs bundle moduli spaces, arXiv:1809.05732 [math.AG], 2018.

Cf. A022553, A145855, A254593.

A131868 := proc(n) local a,d ; a := 0 ; for d in numtheory[divisors](n) do a := a+(-1)^(n+d)*numtheory[mobius](n/d)*binomial(2*d,d) ; od: a/2/n^2 ; end: seq(A131868(n),n=1..30) ; # R. J. Mathar, Oct 24 2007

a = {}; For[n = 1, n < 30, n++, b = Divisors[n]; s = 0; For[j = 1, j < Length[b] + 1, j++, s = s + (-1)^(n + b[[j]])*MoebiusMu[n/b[[j]]]* Binomial[2*b[[j]], b[[j]]]]; AppendTo[a, s/(2*n^2)]]; a (* Stefan Steinerberger, Oct 26 2007 *)
a[n_] := 1/(2n^2) DivisorSum[n, (-1)^(n+#) MoebiusMu[n/#] Binomial[2#, #]& ]; Array[a, 30] (* Jean-François Alcover, Dec 18 2015 *)

a(n) = (2*n^2)^(-1)*sumdiv(n, d, (-1)^(n+d)*moebius(n/d)*binomial(2*d,d)); \\ Michel Marcus, Dec 06 2018

a(n) ~ 2^(2*n - 1) / (sqrt(Pi) * n^(5/2)). - Vaclav Kotesovec, Jun 08 2019

More terms from R. J. Mathar and Stefan Steinerberger, Oct 24 2007

A227532 Logarithmic derivative, wrt x, of triangle A227543, as read by terms k=0..n*(n-1)/2 in rows n>=1.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 3, 1, 4, 6, 8, 8, 4, 4, 1, 5, 10, 15, 20, 20, 20, 15, 10, 5, 5, 1, 6, 15, 26, 39, 48, 57, 60, 54, 48, 36, 30, 18, 12, 6, 6, 1, 7, 21, 42, 70, 98, 126, 154, 168, 175, 168, 154, 133, 112, 84, 70, 49, 35, 21, 14, 7, 7, 1, 8, 28, 64, 118, 184, 256, 336, 408, 472, 516, 536, 532, 504, 464, 408, 360, 296, 248, 192, 152, 112, 88, 56, 40, 24, 16, 8, 8

Offset: 1

Paul D. Hanna, Jul 14 2013

nonn

			L.g.f.: L(x,q) = x*(1) + x^2*(1 + 2*q)/2 + x^3*(1 + 3*q + 3*q^2 + 3*q^3)/3
+ x^4*(1 + 4*q + 6*q^2 + 8*q^3 + 8*q^4 + 4*q^5 + 4*q^6)/4
+ x^5*(1 + 5*q + 10*q^2 + 15*q^3 + 20*q^4 + 20*q^5 + 20*q^6 + 15*q^7 + 10*q^8 + 5*q^9 + 5*q^10)/5
+ x^6*(1 + 6*q + 15*q^2 + 26*q^3 + 39*q^4 + 48*q^5 + 57*q^6 + 60*q^7 + 54*q^8 + 48*q^9 + 36*q^10 + 30*q^11 + 18*q^12 + 12*q^13 + 6*q^14 + 6*q^15)/6 +...
where exponentiation yields the g.f. of triangle A227543:
exp(L(x,q)) = 1 + x*(1) + x^2*(1 + q) + x^3*(1 + 2*q + q^2 + q^3)
+ x^4*(1 + 3*q + 3*q^2 + 3*q^3 + 2*q^4 + q^5 + q^6)
+ x^5*(1 + 4*q + 6*q^2 + 7*q^3 + 7*q^4 + 5*q^5 + 5*q^6 + 3*q^7 + 2*q^8 + q^9 + q^10)
+ x^6*(1 + 5*q + 10*q^2 + 14*q^3 + 17*q^4 + 16*q^5 + 16*q^6 + 14*q^7 + 11*q^8 + 9*q^9 + 7*q^10 + 5*q^11 + 3*q^12 + 2*q^13 + q^14 + q^15) +...
This triangle begins:
1;
1, 2;
1, 3, 3, 3;
1, 4, 6, 8, 8, 4, 4;
1, 5, 10, 15, 20, 20, 20, 15, 10, 5, 5;
1, 6, 15, 26, 39, 48, 57, 60, 54, 48, 36, 30, 18, 12, 6, 6;
1, 7, 21, 42, 70, 98, 126, 154, 168, 175, 168, 154, 133, 112, 84, 70, 49, 35, 21, 14, 7, 7;
1, 8, 28, 64, 118, 184, 256, 336, 408, 472, 516, 536, 532, 504, 464, 408, 360, 296, 248, 192, 152, 112, 88, 56, 40, 24, 16, 8, 8;
1, 9, 36, 93, 189, 324, 489, 684, 891, 1101, 1305, 1476, 1611, 1683, 1701, 1665, 1593, 1476, 1350, 1197, 1053, 900, 765, 630, 522, 405, 324, 243, 189, 135, 99, 63, 45, 27, 18, 9, 9; ...

Paul D. Hanna, Table of n, a(n) for n = 1..1350 (rows n=1..20 of triangle, flattened).
Stéphane Ouvry and Alexios P. Polychronakos, Exclusion statistics for particles with a discrete spectrum, arXiv:2105.14042 [cond-mat.stat-mech], 2021.

Cf. A227543, A145855, A001700, A153338.

{T(n, k)=local(A=1); for(i=1, n, A=1+x*subst(A, x, q*x)*A +x*O(x^n)); n*polcoeff(polcoeff(log(A), n, x), k, q)}
for(n=1, 10, for(k=0, n*(n-1)/2, print1(T(n, k), ", ")); print(""))

/* By Ramanujan's continued fraction identity: */
{T(n, k)=local(P=1, Q=1);
P=sum(m=0, n+1, q^(m^2)*(-x)^m/prod(k=1, m, 1-q^k) +O(x^(n+2)));
Q=sum(m=0, n+1, q^(m*(m-1))*(-x)^m/prod(k=1, m, 1-q^k) +O(x^(n+2)));
polcoeff(polcoeff(P'/P - Q'/Q, n-1, x), k, q)}
for(n=1, 10, for(k=0, n*(n-1)/2, print1(T(n, k), ", ")); print("")) \\ Paul D. Hanna, Dec 28 2016

L.g.f.: Sum_{k=0..n*(n-1)/2, n>=1} T(n,k)*x^n*q^k/n = Log(G(x,q)) where G(x,q) = 1 + x*G(q*x,q)*G(x,q) is the g.f. of triangle A227543.
Row sums form A001700, the logarithmic derivative of the Catalan numbers.
Sum_{k=0..n*(n-1)/2} T(n,k) = binomial(2*n-1, n-1), for n>=1.
Sum_{k=0..n*(n-1)/2} T(n,k)*(-1)^k = (-1)^[n/2] * binomial(n-1, [(n-1)/2]).
Sum_{k=0..n*(n-1)/2} k*T(n,k) = n*2^(2*n-2) - (2*n-1)*binomial(2*n-2,n-1) = A153338(n), for n>=1.
Sum_{k=0..n*(n-1)/2} T(n,k)*exp(2*Pi*I*k/n) = (-1)^(n-1) for n>=1; i.e., the n-th row sum at q = exp(2Pi*I/n), the n-th root of unity, equals -(-1)^n for n>=1.
Sum_{k=0..[n/2]} T(n, n*k) = A145855(n), the number of n-member subsets of 1..2n-1 whose elements sum to a multiple of n.
L.g.f. satisfies: L'(x,q) = P'(x,q)/P(x,q) - Q'(x,q)/Q(x,q), where
  P(x,q) = Sum_{n>=0} q^(n^2) * (-x)^n / Product_{k=1..n} (1-q^k),
  Q(x,q) = Sum_{n>=0} q^(n*(n-1)) * (-x)^n / Product_{k=1..n} (1-q^k),
due to Ramanujan's continued fraction identity. - Paul D. Hanna, Dec 28 2016

cp's OEIS Frontend

A000571 Number of different score sequences that are possible in an n-team round-robin tournament.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A309148 A(n,k) is (1/k) times the number of n-member subsets of [k*n] whose elements sum to a multiple of n; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A169888 Number of n-member subsets of 1..2n whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A131868 a(n) = (2*n^2)^(-1)*Sum_{d|n} (-1)^(n+d)*moebius(n/d)*binomial(2*d,d).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A227532 Logarithmic derivative, wrt x, of triangle A227543, as read by terms k=0..n*(n-1)/2 in rows n>=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A131868 a(n) = (2n^2)^(-1)Sum_{d|n} (-1)^(n+d)moebius(n/d)binomial(2*d,d).