|
Search: id:A069918
|
|
|
| A069918 |
|
Number of ways of partitioning the set {1...n} into two subsets whose sums are as nearly equal as possible. |
|
+0
2
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1.
|
|
REFERENCES
|
Brian Hayes, "The Easiest Hard Problem," American Scientist, Vol. 90, No. 2, March-April 2002, pp. 113-117.
|
|
LINKS
|
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 (se16(AT)btinternet.com), 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.
|
|
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 this_sequence A075380 A078439 A007063
Adjacent sequences: A069915 A069916 A069917 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
