%I #36 May 02 2021 05:38:27
%S 1,1,2,3,4,6,7,11,12,17,19,29,25,41,41,58,56,84,75,117,99,149,140,211,
%T 172,259,237,334,292,434,348,547,465,664,588,836,681,1014,873,1243,
%U 1039,1502,1224,1822,1507,2094,1810,2605,2118,3038,2516
%N Number of knapsack partitions of n.
%C A knapsack partition is a partition such that for every integer there is at most one way to write it as a sum of a subset of the parts of the partition.
%C Equivalently, a knapsack partition of n is a multiset of positive integers summing to n such that every distinct submultiset has a different sum. - _Gus Wiseman_, Oct 03 2015
%H Fausto A. C. Cariboni, <a href="/A108917/b108917.txt">Table of n, a(n) for n = 0..700</a> (terms 0..165 from Vladimir A. Shlyk and A. S. Vroublevski)
%H R. Ehrenborg and M. Readdy, <a href="http://dx.doi.org/10.1016/j.aam.2006.08.006">The Mobius function of partitions with restricted block sizes</a>, Advances in Applied Mathematics, Volume 39, Issue 3, September 2007, Pages 283-292.
%H Vladimir A. Shlyk, <a href="https://arxiv.org/abs/1805.07989">Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number</a>, arXiv:1805.07989 [math.CO], 2018.
%e a(4) = 4, since there are 5 partitions of 4 (see sequence A000041) and the partition 211 is the only partition of these that is not knapsack since 2=1+1.
%e The a(5) = 6 knapsack partitions of 5 are {{5},{3,2},{4,1},{2,2,1},{3,1,1},{1,1,1,1,1}}.
%p g:= proc(n, k) option remember;
%p # list of pairs [multiset, generator] of knapsack partitions of n with max part k
%p local res, i,p,p2;
%p if k = 1 then return [[[n],add(x^i,i=0..n)]] fi;
%p res:= NULL;
%p for i from 0 to floor(n/k) do
%p for p in procname(n-k*i,k-1) do
%p p2:= p[2]*add(x^(k*j),j=0..i);
%p if max(coeffs(expand(p2))) <= 1 then
%p res:= res, [[op(p[1]),i],p2]
%p fi
%p od
%p od;
%p [res];
%p end proc:
%p 1, seq(nops(g(n,n)), n=1..60); # _Robert Israel_, Oct 04 2015
%t ksQ[ptn_] := UnsameQ @@ Plus @@@ Union[Subsets[ptn]];
%t ksAll[n_Integer] :=
%t ksAll[n] =
%t If[n <= 0, {},
%t With[{loe = Array[ksAll, n - 1, 1, Join]},
%t Union[{{n}},
%t Select[Sort[Append[#, n - Plus @@ #], Greater] & /@ loe, ksQ]]]];
%t ksAll[5](*example*)
%t Array[Length[ksAll[#]] &, 20](*sequence*) (* _Gus Wiseman_, Oct 02 2015 *)
%Y Cf. A000041, A275972 (strict knapsack partitions).
%K nonn
%O 0,3
%A _Richard Ehrenborg_, Jul 20 2005