A320052 - OEIS

%I #8 Oct 05 2018 11:11:55

%S 1,0,1,1,1,2,3,3,4,4,6,8,8

%N Number of product-sum knapsack partitions of n. Number of integer partitions y of n such that every product of sums of the parts of a multiset partition of any submultiset of y is distinct.

%e The sequence of product-sum knapsack partitions begins:

%e    0: ()

%e    1:

%e    2: (2)

%e    3: (3)

%e    4: (4)

%e    5: (5) (3,2)

%e    6: (6) (4,2) (3,3)

%e    7: (7) (5,2) (4,3)

%e    8: (8) (6,2) (5,3) (4,4)

%e    9: (9) (7,2) (6,3) (5,4)

%e   10: (10) (8,2) (7,3) (6,4) (5,5) (4,3,3)

%e   11: (11) (9,2) (8,3) (7,4) (6,5) (5,4,2) (5,3,3) (4,4,3)

%e   12: (12) (10,2) (9,3) (8,4) (7,5) (7,3,2) (6,6) (4,4,4)

%e A complete list of all products of sums of multiset partitions of submultisets of (4,3,3) is:

%e            () = 1

%e           (3) = 3

%e           (4) = 4

%e         (3+3) = 6

%e         (3+4) = 7

%e       (3+3+4) = 10

%e       (3)*(3) = 9

%e       (3)*(4) = 12

%e     (3)*(3+4) = 21

%e     (4)*(3+3) = 24

%e   (3)*(3)*(4) = 36

%e These are all distinct, so (4,3,3) is a product-sum knapsack partition of 10.

%t sps[{}]:={{}};

%t sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

%t rrsuks[n_]:=Select[IntegerPartitions[n],Function[q,UnsameQ@@Apply[Times,Apply[Plus,Union@@mps/@Union[Subsets[q]],{2}],{1}]]];

%t Table[Length[rrsuks[n]],{n,12}]

%Y Cf. A001970, A066739, A108917, A275972, A292886, A316313, A318949, A319318, A319320, A319910, A319913.

%Y Cf. A267597, A320053, A320054, A320055, A320056, A320057, A320058.

%K nonn,more

%O 0,6

%A _Gus Wiseman_, Oct 04 2018