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

Prog

(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

Crossrefs

Cf. A122768, A063834, A262671.

Sequence in context: A245268 A117071 A019459 * A274233 A369576 A256209

Adjacent sequences: A276021 A276022 A276023 * A276025 A276026 A276027

Keyword

nonn

Author

Gus Wiseman, Aug 16 2016

Status

approved