OFFSET
1,2
COMMENTS
For a multiset p of positive integers summing to n, a pair (t,p) is defined to be a positive subset sum if there exists a nonempty submultiset of p summing to t. Positive integers with positive subset sums form a multiorder. This sequence is dominated by A122768 (submultisets of integer partitions of n).
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 1..150
Konstantinos Koiliaris and Chao Xu, A Faster Pseudopolynomial Time Algorithm for Subset Sum, arXiv:1507.02318 [cs.DS], 2015-2016.
Gus Wiseman, Comcategories and Multiorders (pdf version)
EXAMPLE
The a(4)=14 positive subset sums are: {(4,4), (1,31), (3,31), (4,31), (2,22), (4,22), (1,211), (2,211), (3,211), (4,211), (1,1111), (2,1111), (3,1111), (4,1111)}.
MATHEMATICA
sums[ptn_?OrderedQ]:=sums[ptn]=If[Length[ptn]===1, ptn, Module[{pri, sms},
pri=Union[Table[Delete[ptn, i], {i, Length[ptn]}]];
sms=Join[sums[#], sums[#]+Total[ptn]-Total[#]]&/@pri;
Union@@sms
]];
Table[Total[Length[sums[Sort[#]]]&/@IntegerPartitions[n]], {n, 1, 25}]
(* Second program: *)
b[n_, i_, s_] := b[n, i, s] = If[n == 0, Length[s], If[i < 1, 0, b[n, i - 1, s] + b[n - i, Min[n - i, i], {#, # + i}& /@ s // Flatten // Union]]];
a[n_] := b[n, n, {0}] - PartitionsP[n];
PROG
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 16 2016
STATUS
approved