The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A145855 Number of n-element subsets of {1,2,...,2n-1} 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,...,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. 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_{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 EXAMPLE 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 +... MATHEMATICA 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 *) 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 27 04:21 EST 2020. Contains 338677 sequences. (Running on oeis4.)