|
|
A108917
|
|
Number of knapsack partitions of n.
|
|
265
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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
|
|
LINKS
|
|
|
EXAMPLE
|
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}}.
|
|
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:
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|