A326033 Number of knapsack partitions of n such that no addition of one part equal to an existing part is knapsack.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 1, 1, 0, 3, 0, 0, 1, 1, 0, 8, 0, 8, 4, 3, 0, 11, 5, 3, 4, 5, 0, 30, 2, 9, 9, 20, 3, 37, 6, 18, 16, 37, 20, 71, 12, 37, 40

Offset

1,21

Comments

An integer partition is knapsack if every distinct submultiset has a different sum.

Links

Table of n, a(n) for n=1..60.

Example

The partition (10,8,6,6) is counted under a(30) because (10,10,8,6,6), (10,8,8,6,6), and (10,8,6,6,6) are not knapsack.

Mathematica

sums[ptn_]:=sums[ptn]=If[Length[ptn]==1, ptn, Union@@(Join[sums[#], sums[#]+Total[ptn]-Total[#]]&/@Union[Table[Delete[ptn, i], {i, Length[ptn]}]])];
ksQ[y_]:=Length[sums[Sort[y]]]==Times@@(Length/@Split[Sort[y]]+1)-1;
maxks[n_]:=Select[IntegerPartitions[n], ksQ[#]&&Select[Table[Sort[Append[#, i]], {i, Union[#]}], ksQ]=={}&];
Table[Length[maxks[n]], {n, 30}]

Crossrefs

Cf. A002033, A108917, A275972, A276024, A299702.

Cf. A325857, A325862, A325863, A325864, A325865, A326015, A326016, A326018.

Sequence in context: A216654 A364014 A326016 * A029429 A064559 A340998

Adjacent sequences: A326030 A326031 A326032 * A326034 A326035 A326036

Keyword

nonn,more

Author

Gus Wiseman, Jun 03 2019

Status

approved