|
%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
|
