A275972 Number of strict knapsack partitions of n.

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

Offset: 0

Author

Gus Wiseman, Aug 15 2016

Keywords

• nonn

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)

Examples

			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
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 0..900 (terms 0..101 from Alois P. Heinz, terms 102..500 from Bert Dobbelaere)

Crossrefs

Cf. A000009, A000041, A108917, A201052, A335357 (the same for compositions).

Programs

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]

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.