cp's OEIS Frontend

A304792 Number of subset-sums of integer partitions of n.

%I A304792 #23 Apr 04 2025 22:29:02
%S A304792 1,2,5,10,19,34,58,96,152,240,361,548,795,1164,1647,2354,3243,4534,
%T A304792 6150,8420,11240,15156,19938,26514,34513,45260,58298,75704,96515,
%U A304792 124064,157072,199894,251097,317278,395625,496184,615229,765836,944045,1168792,1432439
%N A304792 Number of subset-sums of integer partitions of n.
%C A304792 For a multiset p of positive integers summing to n, a pair (t,p) is defined to be a subset sum if there exists a submultiset of p summing to t. This sequence is dominated by A122768 + A000041 (number of submultisets of integer partitions of n).
%H A304792 Robert Price, <a href="/A304792/b304792.txt">Table of n, a(n) for n = 0..70</a>
%F A304792 a(n) = A276024(n) + A000041(n).
%e A304792 The a(4)=19 subset sums are (0,4), (4,4), (0,31), (1,31), (3,31), (4,31), (0,22), (2,22), (4,22), (0,211), (1,211), (2,211), (3,211), (4,211), (0,1111), (1,1111), (2,1111), (3,1111), (4,1111).
%p A304792 b:= proc(n, i, s) option remember; `if`(n=0, nops(s),
%p A304792      `if`(i<1, 0, b(n, i-1, s)+b(n-i, min(n-i, i),
%p A304792       map(x-> [x, x+i][], s))))
%p A304792     end:
%p A304792 a:= n-> b(n$2, {0}):
%p A304792 seq(a(n), n=0..40);  # _Alois P. Heinz_, May 18 2018
%t A304792 Table[Total[Length[Union[Total/@Subsets[#]]]&/@IntegerPartitions[n]],{n,15}]
%t A304792 (* Second program: *)
%t A304792 b[n_, i_, s_] := b[n, i, s] = If[n == 0, Length[s],
%t A304792      If[i < 1, 0, b[n, i - 1, s] + b[n - i, Min[n - i, i],
%t A304792      {#, # + i}& /@ s // Flatten // Union]]];
%t A304792 a[n_] := b[n, n, {0}];
%t A304792 a /@ Range[0, 40] (* _Jean-François Alcover_, May 20 2021, after _Alois P. Heinz_ *)
%o A304792 (Python)
%o A304792 from functools import lru_cache
%o A304792 @lru_cache(maxsize=None)
%o A304792 def A304792_T(n,i,s,l):
%o A304792     if n==0: return l
%o A304792     if i<1: return 0
%o A304792     return A304792_T(n,i-1,s,l)+A304792_T(n-i,min(n-i,i),(t:=tuple(sorted(set(s+tuple(x+i for x in s))))),len(t))
%o A304792 def A304792(n): return A304792_T(n,n,(0,),1) # _Chai Wah Wu_, Sep 25 2023, after _Alois P. Heinz_
%Y A304792 Cf. A000041, A108917, A122768, A276024, A284640, A299701, A301856, A301934, A301979, A304793.
%K A304792 nonn
%O A304792 0,2
%A A304792 _Gus Wiseman_, May 18 2018