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

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

Author

N. J. A. Sloane

Keywords

• nonn
• nice

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

Examples

			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)
		

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.

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.

Programs

Haskell

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

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 *)

PARI

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

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)

Extensions

More terms from Michael Somos, Jun 10 2000