login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A275972 Number of strict knapsack partitions of n. 46
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

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, n-1, 1, Join]}, Union[{{n}}, Select[Sort[Append[#, n-Plus@@#], Greater]&/@loe, sksQ]]]];

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

CROSSREFS

Cf. A000009, A000041, A108917, A201052.

Sequence in context: A274168 A116575 A244800 * A090492 A239949 A103609

Adjacent sequences:  A275969 A275970 A275971 * A275973 A275974 A275975

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 15 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 21 07:23 EDT 2019. Contains 321367 sequences. (Running on oeis4.)