login
Number of knapsack factorizations of n.
32

%I #15 Oct 29 2017 02:35:50

%S 1,1,1,2,1,2,1,3,2,2,1,4,1,2,2,4,1,4,1,4,2,2,1,7,2,2,3,4,1,5,1,6,2,2,

%T 2,8,1,2,2,7,1,5,1,4,4,2,1,11,2,4,2,4,1,7,2,7,2,2,1,11,1,2,4,7,2,5,1,

%U 4,2,5,1,15,1,2,4,4,2,5,1,11,4,2,1,11,2

%N Number of knapsack factorizations of n.

%C A knapsack factorization is a finite multiset of positive integers greater than one such that every distinct submultiset has a different product.

%C The sequence giving the number of factorizations of n is described as "the multiplicative partition function" (see A001055), so knapsack factorizations are a multiplicative generalization of knapsack partitions. - _Gus Wiseman_, Oct 24 2017

%H Vincenzo Librandi, <a href="/A292886/b292886.txt">Table of n, a(n) for n = 1..2000</a>

%e The a(36) = 8 factorizations are 2*2*3*3, 2*2*9, 2*18, 3*3*4, 3*12, 4*9, 6*6, 36. The factorization 2*3*6 is not knapsack.

%t postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];

%t Table[Length[Select[postfacs[n],UnsameQ@@Times@@@Union[Subsets[#]]&]],{n,100}]

%Y Cf. A001055, A045778, a(p^n) = A108917(n), A162247, A259936, A275972, A281116.

%K nonn

%O 1,4

%A _Gus Wiseman_, Sep 26 2017