%I #58 Jul 14 2022 02:27:03
%S 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 77,87,105,100,134,139,145,194,170,192,250
%N 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 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a267/A267597.java">Java program</a> (github)
%e The sequence of product-sum knapsack partitions begins:
%e 0: ()
%e 1: (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)
%e The partition (4,4,3) is not a sum-product knapsack partition of 11 because (4*4) = (4)+(4*3).
%e A complete list of all sums of products of multiset partitions of submultisets of (5,4,2) is:
%e 0 = 0
%e (2) = 2
%e (4) = 4
%e (5) = 5
%e (2*4) = 8
%e (2*5) = 10
%e (4*5) = 20
%e (2*4*5) = 40
%e (2)+(4) = 6
%e (2)+(5) = 7
%e (2)+(4*5) = 22
%e (4)+(5) = 9
%e (4)+(2*5) = 14
%e (5)+(2*4) = 13
%e (2)+(4)+(5) = 11
%e These are all distinct, so (5,4,2) is a sum-product knapsack partition of 11.
%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 rrtuks[n_]:=Select[IntegerPartitions[n],Function[q,UnsameQ@@Apply[Plus,Apply[Times,Union@@mps/@Union[Subsets[q]],{2}],{1}]]];
%t Table[Length[rrtuks[n]],{n,12}]
%Y Cf. A001970, A066739, A108917, A275972, A292886, A316313, A318949, A319318, A319320, A319910, A319913.
%Y Cf. A320052, A320053, A320054, A320055, A320056, A320057, A320058.
%K nonn,more
%O 0,6
%A _Gus Wiseman_, Oct 04 2018
%E a(13)-a(37) from _Sean A. Irvine_, Jul 13 2022
|