A309148 -id:A309148 - cp's OEIS frontend

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

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

A308667 (1/n) times the number of n-member subsets of [n^2] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 1, 10, 115, 2126, 54086, 1753074, 69159399, 3220837534, 173103073384, 10551652603526, 719578430425845, 54297978110913252, 4492502634538340722, 404469190271900056316, 39370123445405248353743, 4120204305690280446004838, 461365717080848755611811094

Offset: 1

Alois P. Heinz, Jul 14 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..339
Romeo Meštrović, Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862-2011), arXiv:1111.3057 [math.NT], 2011.

Main diagonal of A309148.

Cf. A304482, A318557, A318477.

with(numtheory):
a:= proc(n) option remember; add(phi(n/d)*
      (-1)^(n+d)*binomial(n*d, d), d=divisors(n))/n^2
    end:
seq(a(n), n=1..20);

a[n_] := a[n] = Sum[EulerPhi[n/d]*
     (-1)^(n + d)*Binomial[n*d, d], {d, Divisors[n]}]/n^2;
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Mar 24 2022, after Alois P. Heinz *)

a(n) = A309148(n,n).
a(n) = (1/n) * A318477(n).
a(p) == 1 (mod p^3) for all primes p >= 5 (apply Meštrović, Remark 17, p. 12). - Peter Bala, Mar 28 2023
a(n) ~ exp(n - 1/2) * n^(n - 5/2) / sqrt(2*Pi). - Vaclav Kotesovec, Mar 28 2023

A309182 (1/3) times the number of n-member subsets of [3n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 2, 10, 42, 201, 1028, 5538, 30666, 173593, 1001402, 5864750, 34769364, 208267320, 1258574116, 7663720710, 46976034378, 289628805623, 1794932294978, 11175157356522, 69864075597442, 438403736549145, 2760351027094300, 17433869214973754, 110420300879752980

Offset: 1

Alois P. Heinz, Jul 15 2019

nonn

Also (1/2) times the number of n-member subsets of [3n-1] whose elements sum to a multiple of n.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Column k=3 of A309148.

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

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

A309183 (1/4) times the number of n-member subsets of [4n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 3, 19, 115, 776, 5601, 42288, 328755, 2615104, 21191128, 174303163, 1451430673, 12211799224, 103655906784, 886568153744, 7633233556275, 66105170315084, 575445689884848, 5032380942945322, 44191451788247640, 389514699013012242, 3444925385161998521

Offset: 1

Alois P. Heinz, Jul 15 2019

nonn

Also (1/3) times the number of n-member subsets of [4n-1] whose elements sum to a multiple of n.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Column k=4 of A309148.

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

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

A309184 (1/5) times the number of n-member subsets of [5n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 4, 31, 244, 2126, 19780, 192130, 1922740, 19692535, 205444504, 2175519380, 23322657460, 252631900236, 2760767859784, 30400169157656, 336977765092788, 3757141504436393, 42107201575818028, 474084628585822413, 5359833704140818744, 60823006052351729266

Offset: 1

Alois P. Heinz, Jul 15 2019

nonn

Also (1/4) times the number of n-member subsets of [5n-1] whose elements sum to a multiple of n.

Alois P. Heinz, Table of n, a(n) for n = 1..925

Column k=5 of A309148.

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

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

A309185 (1/6) times the number of n-member subsets of [6n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 5, 46, 445, 4751, 54086, 642342, 7861661, 98480332, 1256564755, 16273981758, 213378975958, 2826867619109, 37782552518478, 508840821830546, 6898459216311581, 94070535317459018, 1289430373107971804, 17755914760643605782, 245518560760433579195

Offset: 1

Alois P. Heinz, Jul 15 2019

nonn

Also (1/5) times the number of n-member subsets of [6n-1] whose elements sum to a multiple of n.

Alois P. Heinz, Table of n, a(n) for n = 1..856

Column k=6 of A309148.

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

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

A309186 (1/7) times the number of n-member subsets of [7n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 6, 64, 734, 9276, 124872, 1753074, 25366334, 375677659, 5667202856, 86775157140, 1345153548200, 21069043965984, 332927798516620, 5301031234085664, 84967018635587774, 1369846562874360887, 22199151535757780226, 361411377745122110422, 5908312923795257322184

Offset: 1

Alois P. Heinz, Jul 15 2019

nonn

Also (1/6) times the number of n-member subsets of [7n-1] whose elements sum to a multiple of n.

Alois P. Heinz, Table of n, a(n) for n = 1..806

Column k=7 of A309148.

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

a(n) = 1/(7*n) * sumdiv(n, d, binomial(7*d,d)*(-1)^(n+d)*eulerphi(n/d)); \\ Michel Marcus, Jul 18 2019

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

A309187 (1/8) times the number of n-member subsets of [8n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 7, 85, 1127, 16451, 255619, 4141383, 69159399, 1182125128, 20581143157, 363704640476, 6506965279907, 117626432708864, 2145180354493281, 39421026305282660, 729242353169440743, 13568988503585900648, 253785064585174334488, 4768543107831461199897

Offset: 1

Alois P. Heinz, Jul 15 2019

nonn

Also (1/7) times the number of n-member subsets of [8n-1] whose elements sum to a multiple of n.

Alois P. Heinz, Table of n, a(n) for n = 1..768

Column k=8 of A309148.

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

a(n) = 1/(8*n) * sumdiv(n, d, binomial(8*d,d)*(-1)^(n+d)*eulerphi(n/d)); \\ Michel Marcus, Jul 18 2019

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

A309188 (1/9) times the number of n-member subsets of [9n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 8, 109, 1640, 27151, 478232, 8782075, 166237160, 3220837534, 63562714008, 1273237637706, 25820645555000, 529080420540114, 10937268134114568, 227824992158991334, 4777204094770874856, 100757627271124231383, 2136117417345649876112, 45496022230420668679932

Offset: 1

Alois P. Heinz, Jul 15 2019

nonn

Also (1/8) times the number of n-member subsets of [9n-1] whose elements sum to a multiple of n.

Alois P. Heinz, Table of n, a(n) for n = 1..737

Column k=9 of A309148.

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

a(n) = 1/(9*n) * sumdiv(n, d, binomial(9*d, d)*(-1)^(n+d)*eulerphi(n/d)); \\ Michel Marcus, Jul 19 2019

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

A309189 (1/10) times the number of n-member subsets of [10n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 9, 136, 2289, 42376, 834336, 17125354, 362345361, 7847250409, 173103073384, 3875837737520, 87857163416064, 2012268157890524, 46497242493163450, 1082614775186919136, 25374686712458407441, 598217593341171422090, 14176230568946364963825

Offset: 1

Alois P. Heinz, Jul 15 2019

nonn

Also (1/9) times the number of n-member subsets of [10n-1] whose elements sum to a multiple of n.

Alois P. Heinz, Table of n, a(n) for n = 1..712

Column k=10 of A309148.

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

a(n) = 1/(10*n) * sumdiv(n, d, binomial(10*d, d)*(-1)^(n+d)*eulerphi(n/d)); \\ Michel Marcus, Jul 20 2019

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

cp's OEIS Frontend

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

A308667 (1/n) times the number of n-member subsets of [n^2] whose elements sum to a multiple of n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A309182 (1/3) times the number of n-member subsets of [3n] whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A309183 (1/4) times the number of n-member subsets of [4n] whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A309184 (1/5) times the number of n-member subsets of [5n] whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A309185 (1/6) times the number of n-member subsets of [6n] whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A309186 (1/7) times the number of n-member subsets of [7n] whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A309187 (1/8) times the number of n-member subsets of [8n] whose elements sum to a multiple of n.

Views

Author

Keywords