cp's OEIS Frontend

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

%I A276024 #23 Sep 26 2023 01:59:06
%S A276024 1,3,7,14,27,47,81,130,210,319,492,718,1063,1512,2178,3012,4237,5765,
%T A276024 7930,10613,14364,18936,25259,32938,43302,55862,72694,92797,119499,
%U A276024 151468,193052,242748,307135,383315,481301,597252,744199,918030,1137607,1395101,1718237,2098096,2569047,3121825,3805722
%N A276024 Number of positive subset sums of integer partitions of n.
%C A276024 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).
%H A276024 Fausto A. C. Cariboni, <a href="/A276024/b276024.txt">Table of n, a(n) for n = 1..150</a>
%H A276024 Konstantinos Koiliaris and Chao Xu, <a href="https://arxiv.org/abs/1507.02318">A Faster Pseudopolynomial Time Algorithm for Subset Sum</a>, arXiv:1507.02318 [cs.DS], 2015-2016.
%H A276024 Gus Wiseman, <a href="https://docs.google.com/document/d/1m0s6DGTBkDW9gvMuFmJHvy6oLGRAbQ7okAZcOPZawp0/pub">Comcategories and Multiorders</a> <a href="http://www.nafindix.com/math/academic/ComcategoriesandMultiordersv7.pdf">(pdf version)</a>
%e A276024 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)}.
%t A276024 sums[ptn_?OrderedQ]:=sums[ptn]=If[Length[ptn]===1,ptn,Module[{pri,sms},
%t A276024 pri=Union[Table[Delete[ptn,i],{i,Length[ptn]}]];
%t A276024 sms=Join[sums[#],sums[#]+Total[ptn]-Total[#]]&/@pri;
%t A276024 Union@@sms
%t A276024 ]];
%t A276024 Table[Total[Length[sums[Sort[#]]]&/@IntegerPartitions[n]],{n,1,25}]
%t A276024 (* Second program: *)
%t A276024 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]]];
%t A276024 a[n_] := b[n, n, {0}] - PartitionsP[n];
%t A276024 Array[a, 45] (* _Jean-François Alcover_, May 20 2021, after _Alois P. Heinz_ in A304792 *)
%o A276024 (Python)
%o A276024 # uses A304792_T
%o A276024 from sympy import npartitions
%o A276024 def A276024(n): return A304792_T(n,n,(0,),1) - npartitions(n) # _Chai Wah Wu_, Sep 25 2023
%Y A276024 Cf. A122768, A063834, A262671.
%K A276024 nonn
%O A276024 1,2
%A A276024 _Gus Wiseman_, Aug 16 2016