The OEIS is supported by the many generous donors to the OEIS Foundation.

 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. Mithat Ünsal, Graded Hilbert spaces, quantum distillation and connecting SQCD to QCD, {{arXiv|2104.12352}} [hep-th], 2021. (A145855) 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 26 10:23 EDT 2022. Contains 354879 sequences. (Running on oeis4.)