

A069918


Number of ways of partitioning the set {1...n} into two subsets whose sums are as nearly equal as possible.


7



1, 1, 1, 1, 3, 5, 4, 7, 23, 40, 35, 62, 221, 397, 361, 657, 2410, 4441, 4110, 7636, 28460, 53222, 49910, 93846, 353743, 668273, 632602, 1199892, 4559828, 8679280, 8273610, 15796439, 60400688, 115633260, 110826888, 212681976, 817175698, 1571588177, 1512776590
(list;
graph;
refs;
listen;
history;
text;
internal format)



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, MarchApril 2002, pp. 113117.
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(ni), i1) +b(n+i, i1)))
end:
a:= n> `if`(irem(n1, 4)<2, b(n1, n1) +b(n+1, n1), b(n, n1)):
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

Cf. A060005, A058377, A025591, A063865, A063866, A063867, A306443.
Sequence in context: A082568 A242640 A210195 * A200700 A075380 A248497
Adjacent sequences: A069915 A069916 A069917 * A069919 A069920 A069921


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



