login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #9 Oct 05 2018 11:12:03

%S 1,1,2,3,2,3,4,5,6,8,9,12,14

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

%e The sequence of spanning sum-product knapsack partitions begins:

%e 0: ()

%e 1: (1)

%e 2: (2) (1,1)

%e 3: (3) (2,1) (1,1,1)

%e 4: (4) (3,1)

%e 5: (5) (4,1) (3,2)

%e 6: (6) (5,1) (4,2) (3,3)

%e 7: (7) (6,1) (5,2) (4,3) (3,3,1)

%e 8: (8) (7,1) (6,2) (5,3) (4,4) (3,3,2)

%e 9: (9) (8,1) (7,2) (6,3) (5,4) (4,4,1) (4,3,2) (3,3,3)

%e A complete list of all sums of products covering the parts of (3,3,3,2) is:

%e (2*3*3*3) = 54

%e (2)+(3*3*3) = 29

%e (3)+(2*3*3) = 21

%e (2*3)+(3*3) = 15

%e (2)+(3)+(3*3) = 14

%e (3)+(3)+(2*3) = 12

%e (2)+(3)+(3)+(3) = 11

%e These are all distinct, so (3,3,3,2) is a spanning sum-product knapsack partition of 11.

%e An example of a spanning sum-product knapsack partition that is not a spanning product-sum knapsack partition is (5,4,3,2).

%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 rtuks[n_]:=Select[IntegerPartitions[n],Function[q,UnsameQ@@Apply[Plus,Apply[Times,mps[q],{2}],{1}]]];

%t Table[Length[rtuks[n]],{n,8}]

%Y Cf. A001970, A066739, A108917, A275972, A292886, A316313, A318949, A319318, A319320, A319910, A319913.

%Y Cf. A267597, A320052, A320054, A320055, A320056, A320057, A320058.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Oct 04 2018