login
Number of strict knapsack partitions of n.
123

%I #31 Jan 19 2022 04:35:52

%S 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,

%T 74,108,97,130,116,161,148,201,176,238,224,288,258,354,317,416,373,

%U 501,453,596,525,705,638,833,727,993,876,1148,1007,1336,1199,1583,1366,1816,1607

%N Number of strict knapsack partitions of n.

%C A strict knapsack partition is a set of positive integers summing to n such that every subset has a different sum.

%C 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}.

%C Conjecture: a(n)<a(n+1) iff n is even and positive.

%H Fausto A. C. Cariboni, <a href="/A275972/b275972.txt">Table of n, a(n) for n = 0..900</a> (terms 0..101 from Alois P. Heinz, terms 102..500 from Bert Dobbelaere)

%e 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

%t sksQ[ptn_]:=And[UnsameQ@@ptn,UnsameQ@@Plus@@@Union[Subsets[ptn]]];

%t 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]]]];

%t Array[Length[sksAll[#]]&,20]

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

%K nonn

%O 0,4

%A _Gus Wiseman_, Aug 15 2016