cp's OEIS Frontend

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

%I A267597 #58 Jul 14 2022 02:27:03
%S A267597 1,1,1,1,1,2,3,3,4,4,6,7,8,12,12,14,18,23,23,32,30,35,50,48,47,56,80,
%T A267597 77,87,105,100,134,139,145,194,170,192,250
%N A267597 Number of sum-product knapsack partitions of n. Number of integer partitions y of n such that every sum of products of the parts of a multiset partition of any submultiset of y is distinct.
%H A267597 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a267/A267597.java">Java program</a> (github)
%e A267597 The sequence of product-sum knapsack partitions begins:
%e A267597    0: ()
%e A267597    1: (1)
%e A267597    2: (2)
%e A267597    3: (3)
%e A267597    4: (4)
%e A267597    5: (5) (3,2)
%e A267597    6: (6) (4,2) (3,3)
%e A267597    7: (7) (5,2) (4,3)
%e A267597    8: (8) (6,2) (5,3) (4,4)
%e A267597    9: (9) (7,2) (6,3) (5,4)
%e A267597   10: (10) (8,2) (7,3) (6,4) (5,5) (4,3,3)
%e A267597   11: (11) (9,2) (8,3) (7,4) (6,5) (5,4,2) (5,3,3)
%e A267597 The partition (4,4,3) is not a sum-product knapsack partition of 11 because (4*4) = (4)+(4*3).
%e A267597 A complete list of all sums of products of multiset partitions of submultisets of (5,4,2) is:
%e A267597             0 = 0
%e A267597           (2) = 2
%e A267597           (4) = 4
%e A267597           (5) = 5
%e A267597         (2*4) = 8
%e A267597         (2*5) = 10
%e A267597         (4*5) = 20
%e A267597       (2*4*5) = 40
%e A267597       (2)+(4) = 6
%e A267597       (2)+(5) = 7
%e A267597     (2)+(4*5) = 22
%e A267597       (4)+(5) = 9
%e A267597     (4)+(2*5) = 14
%e A267597     (5)+(2*4) = 13
%e A267597   (2)+(4)+(5) = 11
%e A267597 These are all distinct, so (5,4,2) is a sum-product knapsack partition of 11.
%t A267597 sps[{}]:={{}};
%t A267597 sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A267597 mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
%t A267597 rrtuks[n_]:=Select[IntegerPartitions[n],Function[q,UnsameQ@@Apply[Plus,Apply[Times,Union@@mps/@Union[Subsets[q]],{2}],{1}]]];
%t A267597 Table[Length[rrtuks[n]],{n,12}]
%Y A267597 Cf. A001970, A066739, A108917, A275972, A292886, A316313, A318949, A319318, A319320, A319910, A319913.
%Y A267597 Cf. A320052, A320053, A320054, A320055, A320056, A320057, A320058.
%K A267597 nonn,more
%O A267597 0,6
%A A267597 _Gus Wiseman_, Oct 04 2018
%E A267597 a(13)-a(37) from _Sean A. Irvine_, Jul 13 2022