cp's OEIS Frontend

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

%I A069918 #29 Sep 17 2022 22:15:28
%S A069918 1,1,1,1,3,5,4,7,23,40,35,62,221,397,361,657,2410,4441,4110,7636,
%T A069918 28460,53222,49910,93846,353743,668273,632602,1199892,4559828,8679280,
%U A069918 8273610,15796439,60400688,115633260,110826888,212681976,817175698,1571588177,1512776590
%N A069918 Number of ways of partitioning the set {1...n} into two subsets whose sums are as nearly equal as possible.
%C A069918 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.
%H A069918 Alois P. Heinz, <a href="/A069918/b069918.txt">Table of n, a(n) for n = 1..1000</a>
%H A069918 S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Signum equations and extremal coefficients</a> [broken link]
%H A069918 Steven R. Finch, <a href="/A000980/a000980.pdf">Signum equations and extremal coefficients</a>, February 7, 2009. [Cached copy, with permission of the author]
%H A069918 Brian Hayes, <a href="http://bit-player.org/wp-content/extras/bph-publications/AmSci-2002-03-Hayes-NPP.pdf">The Easiest Hard Problem</a>, American Scientist, Vol. 90, No. 2, March-April 2002, pp. 113-117.
%H A069918 Recreational Mathematics Newsletter, Kolstad, <a href="http://www.uwp.edu/academic/mathematics/usaco/1998/Spring/prob.htm">PROBLEM 4: Subset Sums</a> [broken link]
%H A069918 Dave Rusin, <a href="http://www.math.niu.edu/~rusin/known-math/98/partitions">More Number Theory</a> [broken link]
%F A069918 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
%e A069918 If the triangular number T_n (see A000217) is even then the two totals must be equal, otherwise the two totals differ by one.
%e A069918 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.
%p A069918 b:= proc(n, i) option remember; local m; m:= i*(i+1)/2;
%p A069918       `if`(n>m, 0, `if`(n=m, 1, b(abs(n-i), i-1) +b(n+i, i-1)))
%p A069918     end:
%p A069918 a:= n-> `if`(irem(n-1, 4)<2, b(n-1, n-1) +b(n+1, n-1), b(n, n-1)):
%p A069918 seq(a(n), n=1..60);  # _Alois P. Heinz_, Nov 02 2011
%t A069918 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}]
%t A069918 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}]
%Y A069918 Cf. A060005, A058377, A025591, A063865, A063866, A063867, A306443.
%K A069918 nonn
%O A069918 1,5
%A A069918 _Robert G. Wilson v_, Apr 24 2002
%E A069918 More terms from _Henry Bottomley_, May 08 2002
%E A069918 Comment corrected by _Steven Finch_, Feb 01 2009