A301934 -id:A301934 - cp's OEIS frontend

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

Gus Wiseman, May 18 2018

nonn

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

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

Robert Price, Table of n, a(n) for n = 0..70

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

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

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

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

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

A301935 Number of positive subset-sum trees whose composite a positive subset-sum of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 1, 10, 2, 3, 1, 21, 1, 3, 3, 58, 1, 21, 1, 21, 3, 3, 1, 164, 2, 3, 10, 21, 1, 34, 1, 373, 3, 3, 3, 218, 1, 3, 3, 161, 1, 7, 1, 5, 5, 3, 1, 1320, 2, 5, 3, 5, 1, 7, 3, 7, 3, 3, 1, 7, 1, 3, 4, 2558, 3, 7, 1, 5, 3, 6, 1, 7

Offset: 1

Gus Wiseman, Mar 28 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). A positive subset-sum tree with root x is either the symbol x itself, or is obtained by first choosing a positive subset-sum x <= (y_1,...,y_k) with k > 1 and then choosing a positive subset-sum tree with root y_i for each i = 1...k. The composite of a positive subset-sum tree is the positive subset-sum x <= g where x is the root sum and g is the multiset of leaves. We write positive subset-sum trees in the form rootsum(branch,...,branch). For example, 4(1(1,3),2,2(1,1)) is a positive subset-sum tree with composite 4(1,1,1,2,3) and weight 8.

Gus Wiseman, The a(12) = 21 positive subset-sum trees.

Cf. A000108, A000712, A108917, A122768, A262671, A262673, A275972, A276024, A284640, A299701, A301854, A301855, A301856, A301934.

A316223 Number of subset-sum triangles with composite a subset-sum of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 4, 1, 6, 1, 13, 4, 6, 1, 25, 1, 6, 6, 38, 1, 26, 1, 26, 6, 6

Offset: 1

Gus Wiseman, Jun 27 2018

A positive subset-sum is a pair (h,g), where h is a positive integer and g is an integer partition, such that some submultiset of g sums to h. A triangle consists of a root sum r and a sequence of positive subset-sums ((h_1,g_1),...,(h_k,g_k)) such that the sequence (h_1,...,h_k) is weakly decreasing and has a submultiset summing to r. The composite of a triangle is (r, g_1 + ... + g_k) where + is multiset union.

			We write positive subset-sum triangles in the form rootsum(branch,...,branch). The a(8) = 13 triangles:
  1(1(1,1,1))
  2(2(1,1,1))
  3(3(1,1,1))
  1(1(1),1(1,1))
  2(1(1),1(1,1))
  1(1(1),2(1,1))
  2(1(1),2(1,1))
  3(1(1),2(1,1))
  1(1(1,1),1(1))
  2(1(1,1),1(1))
  1(1(1),1(1),1(1))
  2(1(1),1(1),1(1))
  3(1(1),1(1),1(1))

Cf. A063834, A262671, A269134, A276024, A281113, A299701, A301934, A301935, A316219, A316220, A316222.

A316222 Number of positive subset-sum triangles whose composite is a positive subset-sum of an integer partition of n.

Original entry on oeis.org

1, 5, 20, 74, 258, 855, 2736, 8447

Offset: 1

Gus Wiseman, Jun 27 2018

A positive subset-sum is a pair (h,g), where h is a positive integer and g is an integer partition, such that some submultiset of g sums to h. A triangle consists of a root sum r and a sequence of positive subset-sums ((h_1,g_1),...,(h_k,g_k)) such that the sequence (h_1,...,h_k) is weakly decreasing and has a submultiset summing to r.

			We write positive subset-sum triangles in the form rootsum(branch,...,branch). The a(2) = 5 positive subset-sum triangles:
  2(2(2))
  1(1(1,1))
  2(2(1,1))
  1(1(1),1(1))
  2(1(1),1(1))

Cf. A063834, A262671, A269134, A276024, A281113, A301934, A301935, A316219, A316220.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A301935 Number of positive subset-sum trees whose composite a positive subset-sum of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Links

Crossrefs

A316223 Number of subset-sum triangles with composite a subset-sum of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A316222 Number of positive subset-sum triangles whose composite is a positive subset-sum of an integer partition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs