1,3

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.

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.

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

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

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

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

(PARI) {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

Cf. A000571, A227532.

Column k=2 of A309148.

Sequence in context: A335983 A113682 A291064 * A363448 A373719 A354604

Adjacent sequences: A145852 A145853 A145854 * A145856 A145857 A145858

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

Extension T. D. Noe, Oct 24 2008

approved