login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A320053
Number of spanning 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 y is distinct.
7
1, 1, 2, 3, 2, 3, 4, 5, 6, 8, 9, 12, 14
OFFSET
0,3
EXAMPLE
The sequence of spanning sum-product knapsack partitions begins:
0: ()
1: (1)
2: (2) (1,1)
3: (3) (2,1) (1,1,1)
4: (4) (3,1)
5: (5) (4,1) (3,2)
6: (6) (5,1) (4,2) (3,3)
7: (7) (6,1) (5,2) (4,3) (3,3,1)
8: (8) (7,1) (6,2) (5,3) (4,4) (3,3,2)
9: (9) (8,1) (7,2) (6,3) (5,4) (4,4,1) (4,3,2) (3,3,3)
A complete list of all sums of products covering the parts of (3,3,3,2) is:
(2*3*3*3) = 54
(2)+(3*3*3) = 29
(3)+(2*3*3) = 21
(2*3)+(3*3) = 15
(2)+(3)+(3*3) = 14
(3)+(3)+(2*3) = 12
(2)+(3)+(3)+(3) = 11
These are all distinct, so (3,3,3,2) is a spanning sum-product knapsack partition of 11.
An example of a spanning sum-product knapsack partition that is not a spanning product-sum knapsack partition is (5,4,3,2).
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]]]];
rtuks[n_]:=Select[IntegerPartitions[n], Function[q, UnsameQ@@Apply[Plus, Apply[Times, mps[q], {2}], {1}]]];
Table[Length[rtuks[n]], {n, 8}]
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Oct 04 2018
STATUS
approved