A326015 Number of strict knapsack partitions of n such that no superset with the same maximum is knapsack.

1, 0, 1, 1, 1, 0, 1, 1, 3, 2, 4, 4, 5, 3, 3, 4, 6, 2, 7, 6, 13, 9, 19, 16, 27, 21, 40, 33, 47, 37, 54, 48, 66, 51, 65, 65, 77, 64, 80, 71, 96, 60, 106, 95, 112, 93, 152, 114, 191, 131, 242, 192, 303, 210, 366, 300, 482, 352, 581, 450, 713, 539, 882, 689, 995

Offset

1,9

Comments

An integer partition is knapsack if every distinct submultiset has a different sum.

These are the subsets counted by A325867, ordered by sum rather than maximum.

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..600

Example

The a(1) = 1 through a(17) = 6 strict knapsack partitions (empty columns not shown):
  {1}  {2,1}  {3,1}  {3,2}  {4,2,1}  {5,2,1}  {4,3,2}  {6,3,1}  {5,4,2}
                                              {5,3,1}  {7,2,1}  {6,3,2}
                                              {6,2,1}           {6,4,1}
                                                                {7,3,1}
.
  {5,4,3}  {6,4,3}  {6,5,3}  {6,5,4}    {7,5,4}    {7,6,4}
  {7,3,2}  {6,5,2}  {8,5,1}  {7,6,2}    {9,4,3}    {9,5,3}
  {7,4,1}  {7,4,2}  {9,3,2}  {8,4,2,1}  {9,6,1}    {9,6,2}
  {8,3,1}  {7,5,1}                      {9,4,2,1}  {8,4,3,2}
           {9,3,1}                                 {9,5,2,1}
                                                   {10,4,2,1}

Mathematica

ksQ[y_]:=UnsameQ@@Total/@Union[Subsets[y]]
maxsks[n_]:=Select[Select[IntegerPartitions[n], UnsameQ@@#&&ksQ[#]&], Select[Table[Append[#, i], {i, Complement[Range[Max@@#], #]}], ksQ]=={}&];
Table[Length[maxsks[n]], {n, 30}]

Crossrefs

Cf. A002033, A108917, A275972, A276024.

Cf. A325863, A325864, A325877, A325878, A325880, A326016, A326017, A326018.

Sequence in context: A061901 A322349 A321232 * A078822 A224980 A368677

Adjacent sequences: A326012 A326013 A326014 * A326016 A326017 A326018

Keyword

nonn

Author

Gus Wiseman, Jun 03 2019

Status

approved