login
A326015
Number of strict knapsack partitions of n such that no superset with the same maximum is knapsack.
8
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}]
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 03 2019
STATUS
approved