

A145855


Number of nelement subsets of {1,2,...,2n1} whose elements sum to a multiple of n.


6



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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


LINKS

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.
Shane Chern, An extension of a formula of Jovovic, Integers (2019) Vol. 19, Article A47.
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.


FORMULA

a(n) = (1/(2*n))*Sum_{dn} (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_{dn} (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 nteam roundrobin 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


EXAMPLE

a(3)=4 because, of the 10 3element 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 +...


MATHEMATICA

Table[Length[Select[Plus@@@Subsets[Range[2n1], {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 *)


PROG

(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


CROSSREFS

Cf. A000571, A227532.
Column k=2 of A309148.
Sequence in context: A335983 A113682 A291064 * A240042 A099615 A114618
Adjacent sequences: A145852 A145853 A145854 * A145856 A145857 A145858


KEYWORD

nonn


AUTHOR

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


EXTENSIONS

Extension T. D. Noe, Oct 24 2008


STATUS

approved



