|
%I #50 Mar 28 2023 12:37:59
%S 1,1,4,9,26,76,246,809,2704,9226,32066,112716,400024,1432614,5170604,
%T 18784169,68635478,252085792,930138522,3446167834,12815663844,
%U 47820414962,178987624514,671825133644,2528212128776,9536894664376
%N Number of n-element subsets of {1,2,...,2n-1} whose elements sum to a multiple of n.
%C 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.
%H Seiichi Manyama, <a href="/A145855/b145855.txt">Table of n, a(n) for n = 1..1669</a> (terms 1..200 from T. D. Noe)
%H Max Alekseyev, <a href="/A145855/a145855.txt">Proof of Jovovic's formula</a>, 2008.
%H Shane Chern, <a href="http://math.colgate.edu/~integers/t47/t47.Abstract.html">An extension of a formula of Jovovic</a>, Integers (2019) Vol. 19, Article A47.
%H Anders Claesson, Mark Dukes, Atli Fannar Franklín, and Sigurður Örn Stefánsson, <a href="https://arxiv.org/abs/2209.03925">Counting tournament score sequences</a>, arXiv:2209.03925 [math.CO], 2022.
%H P. Erdős, A. Ginzburg and A. Ziv, <a href="https://pdfs.semanticscholar.org/2860/2b7734c115bbab7141a1942a2c974057ddc0.pdf">Theorem in the additive number theory</a>, Bull. Res. Council Israel 10 (1961).
%H Steven Rayan, <a href="https://arxiv.org/abs/1809.05732">Aspects of the topology and combinatorics of Higgs bundle moduli spaces</a>, arXiv:1809.05732 [math.AG], 2018.
%H Mithat Ünsal, Graded Hilbert spaces, quantum distillation and connecting SQCD to QCD, {{arXiv|2104.12352}} [hep-th], 2021. (A145855)
%F 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).
%F 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
%F a(n) = Sum_{d|n} (-1)^(n+d)*d*A131868(d). - _Vladeta Jovovic_, Oct 28 2008
%F 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
%F 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
%F G.f.: -Sum_{m >= 1} (phi(m)/m) * log((1 + sqrt(1 + 4*(-y)^m))/2). - _Petros Hadjicostas_, Jul 15 2019
%F a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Mar 28 2023
%e 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.
%e 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 +...
%e where exponentiation yields the g.f. of A000571:
%e 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 +...
%t Table[Length[Select[Plus@@@Subsets[Range[2n-1],{n}], Mod[ #,n]==0&]], {n,10}]
%t 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 *)
%o (PARI) {a(n)=sumdiv(n, d, (-1)^(n+d)*eulerphi(n/d)*binomial(2*d, d)/(2*n))}
%o (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)}
%o {a(n)=sum(k=0,n\2, A227532(n, n*k))} \\ _Paul D. Hanna_, Jul 17 2013
%Y Cf. A000571, A227532.
%Y Column k=2 of A309148.
%K nonn
%O 1,3
%A _T. D. Noe_, Oct 21 2008, Oct 22 2008, Oct 24 2008
%E Extension _T. D. Noe_, Oct 24 2008
|
