OFFSET
0,6
EXAMPLE
The sequence of product-sum knapsack partitions begins:
0: ()
1:
2: (2)
3: (3)
4: (4)
5: (5) (3,2)
6: (6) (4,2) (3,3)
7: (7) (5,2) (4,3)
8: (8) (6,2) (5,3) (4,4)
9: (9) (7,2) (6,3) (5,4)
10: (10) (8,2) (7,3) (6,4) (5,5) (4,3,3)
11: (11) (9,2) (8,3) (7,4) (6,5) (5,4,2) (5,3,3) (4,4,3)
12: (12) (10,2) (9,3) (8,4) (7,5) (7,3,2) (6,6) (4,4,4)
A complete list of all products of sums of multiset partitions of submultisets of (4,3,3) is:
() = 1
(3) = 3
(4) = 4
(3+3) = 6
(3+4) = 7
(3+3+4) = 10
(3)*(3) = 9
(3)*(4) = 12
(3)*(3+4) = 21
(4)*(3+3) = 24
(3)*(3)*(4) = 36
These are all distinct, so (4,3,3) is a product-sum knapsack partition of 10.
MATHEMATICA
sps[{}]:={{}};
sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
rrsuks[n_]:=Select[IntegerPartitions[n], Function[q, UnsameQ@@Apply[Times, Apply[Plus, Union@@mps/@Union[Subsets[q]], {2}], {1}]]];
Table[Length[rrsuks[n]], {n, 12}]
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Oct 04 2018
STATUS
approved