|
| |
|
|
A069918
|
|
Number of ways of partitioning the set {1...n} into two subsets whose sums are as nearly equal as possible.
|
|
4
| |
|
|
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; 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.
|
|
|
REFERENCES
| Brian Hayes, "The Easiest Hard Problem," American Scientist, Vol. 90, No. 2, March-April 2002, pp. 113-117.
|
|
|
LINKS
| Alois P. Heinz, Table of n, a(n) for n = 1..1000
S. R. Finch, Signum equations and extremal coefficients.
Recreational Mathematics Newsletter, Kolstad, PROBLEM 4: Subset Sums
Dave Rusin, More Number Theory
|
|
|
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.
Sequence in context: A023859 A096457 A082568 * A200700 A075380 A177983
Adjacent sequences: A069915 A069916 A069917 * A069919 A069920 A069921
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Robert G. Wilson v (rgwv(AT)rgwv.com), Apr 24 2002
|
|
|
EXTENSIONS
| More terms from Henry Bottomley (se16(AT)btinternet.com), May 08 2002
Comment corrected by S. R. Finch (Steven.Finch(AT)inria.fr), Feb 01 2009
|
| |
|
|
