login
Number of ways of writing 0 as Sum_{k=-n..n} e(k)*k, where e(k) is 0 or 1.
(Formerly M1155 N0439)
31

%I M1155 N0439 #82 Oct 28 2023 13:09:12

%S 2,4,8,20,52,152,472,1520,5044,17112,59008,206260,729096,2601640,

%T 9358944,33904324,123580884,452902072,1667837680,6168510256,

%U 22903260088,85338450344,318995297200,1195901750512,4495448217544,16940411201280,63983233268592

%N Number of ways of writing 0 as Sum_{k=-n..n} e(k)*k, where e(k) is 0 or 1.

%C The 4-term sequence 2,4,8,20 is the answer to the "Solitaire Army" problem, or checker-jumping puzzle. It is too short to have its own entry. See Conway et a;., Winning Ways, Vol. 2, pp. 715-717. - _N. J. A. Sloane_, Mar 01 2018

%C Number of subsets of {-n..n} with sum 0. Also the number of subsets of {0..2n} that are empty or have mean n. For median instead of mean we have twice A024718. - _Gus Wiseman_, Apr 23 2023

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 294.

%D E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see pp. 715-717.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Ray Chandler, <a href="/A000980/b000980.txt">Table of n, a(n) for n = 0..1668</a> (terms < 10^1000; terms 0..200 from T. D. Noe, terms 201..400 from Alois P. Heinz)

%H Eunice Y. S. Chan and R. M. Corless, <a href="https://arxiv.org/abs/1606.09132">Narayana, Mandelbrot, and A New Kind of Companion Matrix</a>, arXiv preprint arXiv:1606.09132 [math.CO], 2016.

%H R. C. Entringer, <a href="http://dx.doi.org/10.4153/CMB-1968-036-3">Representation of m as Sum_{k=-n..n} epsilon_k k</a>, Canad. Math. Bull., 11 (1968), 289-293.

%H Steven R. Finch, <a href="/A000980/a000980.pdf">Signum equations and extremal coefficients</a>, February 7, 2009. [Cached copy, with permission of the author]

%H J. H. van Lint, <a href="http://dx.doi.org/10.1090/S0002-9939-1967-0205964-8 ">Representations of 0 as Sum_{k = -N..N} epsilon_k*k</a>, Proc. Amer. Math. Soc., 18 (1967), 182-184.

%F Constant term of Product_{k=-n..n} (1+x^k).

%F a(n) = Sum_i A067059(2n+1-i, i) = 2+2*Sum_j A047997(n, j); i.e., sum of alternate antidiagonals of A067059 and two more than twice row sums of A047997. - _Henry Bottomley_, Aug 11 2002

%F a(n) = A004171(n) - 2*A181765(n).

%F Coefficient of x^(n*(n+1)/2) in 2*Product_{k=1..n} (1+x^k)^2. - _Sean A. Irvine_, Oct 03 2011

%F From _Gus Wiseman_, Apr 23 2023: (Start)

%F a(n) = 2*A047653(n).

%F a(n) = A070925(2n+1) + 1.

%F a(n) = 2*A133406(2n+1).

%F a(n) = 2*(A212352(n) + 1).

%F a(n) = A222955(2n+1).

%F a(n) = 2*(A362046(2n) + 1).

%F (End)

%e From _Gus Wiseman_, Apr 23 2023: (Start)

%e The a(0) = 2 through a(2) = 8 subsets of {-n..n} with sum 0 are:

%e {} {} {}

%e {0} {0} {0}

%e {-1,1} {-1,1}

%e {-1,0,1} {-2,2}

%e {-1,0,1}

%e {-2,0,2}

%e {-2,-1,1,2}

%e {-2,-1,0,1,2}

%e (End)

%p b:= proc(n, i) option remember; `if`(n>i*(i+1)/2, 0,

%p `if`(i=0, 1, 2*b(n, i-1)+b(n+i, i-1)+b(abs(n-i), i-1)))

%p end:

%p a:=n-> 2*b(0, n):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Mar 10 2014

%t a[n_] := SeriesCoefficient[ Product[1+x^k, {k, -n, n}], {x, 0, 0}]; a[0] = 2; Table[a[n], {n, 0, 24}](* _Jean-François Alcover_, Nov 28 2011 *)

%t nmax = 26; d = {2}; a1 = {};

%t Do[

%t i = Ceiling[Length[d]/2];

%t AppendTo[a1, If[i > Length[d], 0, d[[i]]]];

%t d = PadLeft[d, Length[d] + 2 n] + PadRight[d, Length[d] + 2 n] +

%t 2 PadLeft[PadRight[d, Length[d] + n], Length[d] + 2 n];

%t , {n, nmax}];

%t a1 (* _Ray Chandler_, Mar 15 2014 *)

%t Table[Length[Select[Subsets[Range[-n,n]],Total[#]==0&]],{n,0,5}] (* _Gus Wiseman_, Apr 23 2023 *)

%o (PARI) a(n)=polcoeff(prod(k=-n,n,1+x^k),0)

%o (Haskell) a000980 n = length $ filter ((== 0) . sum) $ subsequences [-n..n]

%Y A047653(n) = a(n)/2.

%Y Bisection of A084239. Cf. A063865, A141000.

%Y A007318 counts subsets by length, A327481 by integer mean.

%Y A327475 counts subsets with integer mean, A000975 integer median.

%Y Cf. A024718, A047997, A070925, A079309, A133406, A212352, A359893, A362046.

%K nonn,nice

%O 0,1

%A _N. J. A. Sloane_

%E More terms from _Michael Somos_, Jun 10 2000