A276024 Number of positive subset sums of integer partitions of n.

1, 3, 7, 14, 27, 47, 81, 130, 210, 319, 492, 718, 1063, 1512, 2178, 3012, 4237, 5765, 7930, 10613, 14364, 18936, 25259, 32938, 43302, 55862, 72694, 92797, 119499, 151468, 193052, 242748, 307135, 383315, 481301, 597252, 744199, 918030, 1137607, 1395101, 1718237, 2098096, 2569047, 3121825, 3805722

Offset: 1

Author

Gus Wiseman, Aug 16 2016

Keywords

• nonn

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).

Examples

			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)}.
		

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)

Crossrefs

Cf. A122768, A063834, A262671.

Programs

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];
Array[a, 45] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz in A304792 *)

Python

# uses A304792_T
from sympy import npartitions
def A276024(n): return A304792_T(n,n,(0,),1) - npartitions(n) # Chai Wah Wu, Sep 25 2023