A108917 Number of knapsack partitions of n.

1, 1, 2, 3, 4, 6, 7, 11, 12, 17, 19, 29, 25, 41, 41, 58, 56, 84, 75, 117, 99, 149, 140, 211, 172, 259, 237, 334, 292, 434, 348, 547, 465, 664, 588, 836, 681, 1014, 873, 1243, 1039, 1502, 1224, 1822, 1507, 2094, 1810, 2605, 2118, 3038, 2516

Offset: 0

Author

Richard Ehrenborg, Jul 20 2005

Keywords

• nonn

Comments

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.

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

Examples

			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.
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}}.
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 0..700 (terms 0..165 from Vladimir A. Shlyk and A. S. Vroublevski)
• R. Ehrenborg and M. Readdy, The Mobius function of partitions with restricted block sizes, Advances in Applied Mathematics, Volume 39, Issue 3, September 2007, Pages 283-292.
• Vladimir A. Shlyk, Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number, arXiv:1805.07989 [math.CO], 2018.

Crossrefs

Cf. A000041, A275972 (strict knapsack partitions).

Programs

Maple

g:= proc(n, k) option remember;
# list of pairs [multiset, generator] of knapsack partitions of n with max part k
local res, i,p,p2;
if k = 1 then return [[[n],add(x^i,i=0..n)]] fi;
res:= NULL;
for i from 0 to floor(n/k) do
  for p in procname(n-k*i,k-1) do
     p2:= p[2]*add(x^(k*j),j=0..i);
     if max(coeffs(expand(p2))) <= 1 then
        res:= res, [[op(p[1]),i],p2]
     fi
  od
od;
[res];
end proc:
1, seq(nops(g(n,n)), n=1..60); # Robert Israel, Oct 04 2015

Mathematica

ksQ[ptn_] := UnsameQ @@ Plus @@@ Union[Subsets[ptn]];
ksAll[n_Integer] :=
  ksAll[n] =
   If[n <= 0, {},
    With[{loe = Array[ksAll, n - 1, 1, Join]},
     Union[{{n}},
      Select[Sort[Append[#, n - Plus @@ #], Greater] & /@ loe, ksQ]]]];
ksAll[5](*example*)
Array[Length[ksAll[#]] &, 20](*sequence*) (* Gus Wiseman, Oct 02 2015 *)