login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 22 13:47 EST 2019. Contains 329393 sequences. (Running on oeis4.)