

A275972


Number of strict knapsack partitions of n.


71



1, 1, 1, 2, 2, 3, 3, 5, 5, 8, 7, 11, 11, 15, 14, 21, 20, 28, 26, 38, 35, 51, 45, 65, 61, 82, 74, 108, 97, 130, 116, 161, 148, 201, 176, 238, 224, 288, 258, 354, 317, 416, 373, 501, 453, 596, 525, 705, 638, 833, 727, 993, 876, 1148, 1007, 1336, 1199, 1583, 1366, 1816, 1607
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

A strict knapsack partition is a set of positive integers summing to n such that every subset has a different sum.
Unlike in the nonstrict case (A108917), the multiset of blocksums of any set partition of a strict knapsack partition also form a strict knapsack partition. If p is a strict knapsack partition of n with k parts, then the upper ideal of p in the poset of refinementordered integer partitions of n is isomorphic to the lattice of set partitions of {1,...,k}.
Conjecture: a(n)<a(n+1) iff n is even and positive.


LINKS

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


EXAMPLE

For n=5, there are A000041(5) = 7 sets of positive integers that sum to 5. Four of these have distinct subsets with the same sum: {3,1,1}, {2,2,1}, {2,1,1,1}, and {1,1,1,1,1}. The other three: {5}, {4,1}, and {3,2}, do not have distinct subsets with the same sum. So a(5) = 3.  Michael B. Porter, Aug 17 2016


MATHEMATICA

sksQ[ptn_]:=And[UnsameQ@@ptn, UnsameQ@@Plus@@@Union[Subsets[ptn]]];
sksAll[n_Integer]:=sksAll[n]=If[n<=0, {}, With[{loe=Array[sksAll, n1, 1, Join]}, Union[{{n}}, Select[Sort[Append[#, nPlus@@#], Greater]&/@loe, sksQ]]]];
Array[Length[sksAll[#]]&, 20]


CROSSREFS

Cf. A000009, A000041, A108917, A201052.
Sequence in context: A274168 A116575 A244800 * A090492 A325768 A239949
Adjacent sequences: A275969 A275970 A275971 * A275973 A275974 A275975


KEYWORD

nonn


AUTHOR

Gus Wiseman, Aug 15 2016


STATUS

approved



