A069918 Number of ways of partitioning the set {1...n} into two subsets whose sums are as nearly equal as possible.
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
Offset: 1
Keywords
Examples
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.
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]
Programs
-
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}]
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
Extensions
More terms from Henry Bottomley, May 08 2002
Comment corrected by Steven Finch, Feb 01 2009
Comments