login
Number of knapsack partitions of n.
265

%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