|
%I #11 Oct 05 2018 11:12:12
%S 1,1,2,3,2,4,5,8,10,12,16,17,25
%N Number of spanning product-sum knapsack partitions of n. Number of integer partitions y of n such that every product of sums the parts of a multiset partition of y is distinct.
%e The sequence of spanning product-sum 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) (3,1,1)
%e 6: (6) (5,1) (4,2) (4,1,1) (3,3)
%e 7: (7) (6,1) (5,2) (5,1,1) (4,3) (4,2,1) (4,1,1,1) (3,3,1)
%e 8: (8) (7,1) (6,2) (6,1,1) (5,3) (5,2,1) (5,1,1,1) (4,4) (4,3,1) (3,3,2)
%e 9: (9) (8,1) (7,2) (7,1,1) (6,3) (6,2,1) (6,1,1,1) (5,4) (5,3,1) (4,4,1) (4,3,2) (3,3,3)
%e A complete list of all products of sums covering the parts of (4,1,1,1) is:
%e (1+1+1+4) = 7
%e (1)*(1+1+4) = 6
%e (4)*(1+1+1) = 12
%e (1+1)*(1+4) = 10
%e (1)*(1)*(1+4) = 5
%e (1)*(4)*(1+1) = 8
%e (1)*(1)*(1)*(4) = 4
%e These are all distinct, so (4,1,1,1) is a spanning product-sum knapsack partition of 7.
%e A complete list of all products of sums covering the parts of (5,3,1,1) is:
%e (1+1+3+5) = 10
%e (1)*(1+3+5) = 9
%e (3)*(1+1+5) = 21
%e (5)*(1+1+3) = 25
%e (1+1)*(3+5) = 16
%e (1+3)*(1+5) = 24
%e (1)*(1)*(3+5) = 8
%e (1)*(3)*(1+5) = 18
%e (1)*(5)*(1+3) = 20
%e (3)*(5)*(1+1) = 30
%e (1)*(1)*(3)*(5) = 15
%e These are all distinct, so (5,3,1,1) is a spanning product-sum knapsack partition of 10.
%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 rsuks[n_]:=Select[IntegerPartitions[n],Function[q,UnsameQ@@Apply[Times,Apply[Plus,mps[q],{2}],{1}]]];
%t Table[Length[rsuks[n]],{n,10}]
%Y Cf. A001970, A066739, A108917, A275972, A292886, A316313, A318949, A319318, A319320, A319910, A319913.
%Y Cf. A267597, A320052, A320053, A320055, A320056, A320057, A320058.
%K nonn,more
%O 0,3
%A _Gus Wiseman_, Oct 04 2018
|
