OFFSET

1,5

COMMENTS

If n mod 4 = 0 or 3, a(n) is the number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1; if n mod 4 = 1 or 2, a(n) is half this number.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..1000

S. R. Finch, Signum equations and extremal coefficients [broken link]

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

Brian Hayes, The Easiest Hard Problem, American Scientist, Vol. 90, No. 2, March-April 2002, pp. 113-117.

Recreational Mathematics Newsletter, Kolstad, PROBLEM 4: Subset Sums [broken link]

Dave Rusin, More Number Theory [broken link]

FORMULA

If n mod 4 = 0 or 3 then the two subsets have the same sum and a(n) = A025591(n); if n mod 4 = 1 or 2 then the two subsets have sums which differ by 1 and a(n) = A025591(n)/2. - Henry Bottomley, May 08 2002

EXAMPLE

If the triangular number T_n (see A000217) is even then the two totals must be equal, otherwise the two totals differ by one.

a(6) = 5: T6 = 21 and is odd. There are five sets such that the sum of one side is equal to the other side +/- 1. They are 5+6 = 1+2+3+4, 4+6 = 1+2+3+5, 1+4+6 = 2+3+5, 1+3+6 = 2+4+5 and 2+3+6 = 1+4+5.

MAPLE

b:= proc(n, i) option remember; local m; m:= i*(i+1)/2;

`if`(n>m, 0, `if`(n=m, 1, b(abs(n-i), i-1) +b(n+i, i-1)))

end:

a:= n-> `if`(irem(n-1, 4)<2, b(n-1, n-1) +b(n+1, n-1), b(n, n-1)):

seq(a(n), n=1..60); # Alois P. Heinz, Nov 02 2011

MATHEMATICA

Needs["DiscreteMath`Combinatorica`"]; f[n_] := f[n] = Block[{s = Sort[Plus @@@ Subsets[n]], k = n(n + 1)/2}, If[ EvenQ[k], Count[s, k/2]/2, (Count[s, Floor[k/2]] + Count[s, Ceiling[k/2]]) /2]]; Table[ f[n], {n, 1, 22}]

f[n_, s_] := f[n, s] = Which[n == 0, If[s == 0, 1, 0], Abs[s] > (n*(n + 1))/2, 0, True, f[n - 1, s - n] + f[n - 1, s + n]]; Table[ Which[ Mod[n, 4] == 0 || Mod[n, 4] == 3, f[n, 0]/2, Mod[n, 4] == 1 || Mod[n, 4] == 2, f[n, 1]], {n, 1, 40}]

CROSSREFS

KEYWORD

nonn

AUTHOR

Robert G. Wilson v, Apr 24 2002

EXTENSIONS

More terms from Henry Bottomley, May 08 2002

Comment corrected by Steven Finch, Feb 01 2009

STATUS

approved