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

2, 4, 8, 20, 52, 152, 472, 1520, 5044, 17112, 59008, 206260, 729096, 2601640, 9358944, 33904324, 123580884, 452902072, 1667837680, 6168510256, 22903260088, 85338450344, 318995297200, 1195901750512, 4495448217544, 16940411201280, 63983233268592

Offset

0,1

Comments

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

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

References

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

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

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

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

Links

Ray Chandler, Table of n, a(n) for n = 0..1668 (terms < 10^1000; terms 0..200 from T. D. Noe, terms 201..400 from Alois P. Heinz)

Eunice Y. S. Chan and R. M. Corless, Narayana, Mandelbrot, and A New Kind of Companion Matrix, arXiv preprint arXiv:1606.09132 [math.CO], 2016.

R. C. Entringer, Representation of m as Sum_{k=-n..n} epsilon_k k, Canad. Math. Bull., 11 (1968), 289-293.

Steven R. Finch, Signum equations and extremal coefficients, February 7, 2009. [Cached copy, with permission of the author]

J. H. van Lint, Representations of 0 as Sum_{k = -N..N} epsilon_k*k, Proc. Amer. Math. Soc., 18 (1967), 182-184.

Formula

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

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

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

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

From Gus Wiseman, Apr 23 2023: (Start)

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

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

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

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

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

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

(End)

Example

From Gus Wiseman, Apr 23 2023: (Start)
The a(0) = 2 through a(2) = 8 subsets of {-n..n} with sum 0 are:
  {}   {}        {}
  {0}  {0}       {0}
       {-1,1}    {-1,1}
       {-1,0,1}  {-2,2}
                 {-1,0,1}
                 {-2,0,2}
                 {-2,-1,1,2}
                 {-2,-1,0,1,2}
(End)

Maple

b:= proc(n, i) option remember; `if`(n>i*(i+1)/2, 0,
      `if`(i=0, 1, 2*b(n, i-1)+b(n+i, i-1)+b(abs(n-i), i-1)))
    end:
a:=n-> 2*b(0, n):
seq(a(n), n=0..40); # Alois P. Heinz, Mar 10 2014

Mathematica

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 *)
nmax = 26; d = {2}; a1 = {};
Do[
  i = Ceiling[Length[d]/2];
  AppendTo[a1, If[i > Length[d], 0, d[[i]]]];
  d = PadLeft[d, Length[d] + 2 n] + PadRight[d, Length[d] + 2 n] +
    2 PadLeft[PadRight[d, Length[d] + n], Length[d] + 2 n];
  , {n, nmax}];
a1 (* Ray Chandler, Mar 15 2014 *)
Table[Length[Select[Subsets[Range[-n, n]], Total[#]==0&]], {n, 0, 5}] (* Gus Wiseman, Apr 23 2023 *)

Prog

(PARI) a(n)=polcoeff(prod(k=-n, n, 1+x^k), 0)
(Haskell) a000980 n = length $ filter ((== 0) . sum) $ subsequences [-n..n]

Crossrefs

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

Bisection of A084239. Cf. A063865, A141000.

A007318 counts subsets by length, A327481 by integer mean.

A327475 counts subsets with integer mean, A000975 integer median.

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

Sequence in context: A218088 A222320 A089976 * A123611 A082279 A113180

Adjacent sequences: A000977 A000978 A000979 * A000981 A000982 A000983

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

More terms from Michael Somos, Jun 10 2000

Status

approved