|
| |
|
|
A275972
|
|
Number of strict knapsack partitions of n.
|
|
123
|
|
|
|
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 non-strict case (A108917), the multiset of block-sums 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 refinement-ordered 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
|
|
|
|
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, n-1, 1, Join]}, Union[{{n}}, Select[Sort[Append[#, n-Plus@@#], Greater]&/@loe, sksQ]]]];
Array[Length[sksAll[#]]&, 20]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
