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

1, 2, 5, 10, 19, 34, 58, 96, 152, 240, 361, 548, 795, 1164, 1647, 2354, 3243, 4534, 6150, 8420, 11240, 15156, 19938, 26514, 34513, 45260, 58298, 75704, 96515, 124064, 157072, 199894, 251097, 317278, 395625, 496184, 615229, 765836, 944045, 1168792, 1432439

Offset

0,2

Comments

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

Links

Table of n, a(n) for n=0..40.

Formula

a(n) = A276024(n) + A000041(n).

Example

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

Maple

b:= proc(n, i, s) option remember; `if`(n=0, nops(s),
     `if`(i<1, 0, b(n, i-1, s)+b(n-i, min(n-i, i),
      map(x-> [x, x+i][], s))))
    end:
a:= n-> b(n$2, {0}):
seq(a(n), n=0..40);  # Alois P. Heinz, May 18 2018

Mathematica

Table[Total[Length[Union[Total/@Subsets[#]]]&/@IntegerPartitions[n]], {n, 15}]
(* 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}];
a /@ Range[0, 40] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

Prog

(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def A304792_T(n, i, s, l):
    if n==0: return l
    if i<1: return 0
    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))
def A304792(n): return A304792_T(n, n, (0, ), 1) # Chai Wah Wu, Sep 25 2023, after Alois P. Heinz

Crossrefs

Cf. A000041, A108917, A122768, A276024, A284640, A299701, A301856, A301934, A301979, A304793.

Sequence in context: A132210 A000098 A024827 * A104161 A288579 A065613

Adjacent sequences: A304789 A304790 A304791 * A304793 A304794 A304795

Keyword

nonn

Author

Gus Wiseman, May 18 2018

Status

approved