A366754 Number of non-knapsack integer partitions of n.

0, 0, 0, 0, 1, 1, 4, 4, 10, 13, 23, 27, 52, 60, 94, 118, 175, 213, 310, 373, 528, 643, 862, 1044, 1403, 1699, 2199, 2676, 3426, 4131, 5256, 6295, 7884, 9479, 11722, 14047, 17296, 20623, 25142, 29942, 36299, 43081, 51950, 61439, 73668, 87040, 103748, 122149, 145155, 170487

Offset: 0

Author

Gus Wiseman, Nov 08 2023

Keywords

• nonn

Comments

A multiset is non-knapsack if there exist two different submultisets with the same sum.

Examples

			The a(4) = 1 through a(9) = 13 partitions:
  (211)  (2111)  (321)    (3211)    (422)      (3321)
                 (2211)   (22111)   (431)      (4221)
                 (3111)   (31111)   (3221)     (4311)
                 (21111)  (211111)  (4211)     (5211)
                                    (22211)    (32211)
                                    (32111)    (33111)
                                    (41111)    (42111)
                                    (221111)   (222111)
                                    (311111)   (321111)
                                    (2111111)  (411111)
                                               (2211111)
                                               (3111111)
                                               (21111111)
		

Crossrefs

The complement is counted by A108917, strict A275972, ranks A299702.

These partitions have ranks A299729.

The strict case is A316402.

The binary version is A366753, ranks A366740.

A000041 counts integer partitions, strict A000009.

A276024 counts positive subset-sums of partitions, strict A284640.

A304792 counts subset-sum of partitions, strict A365925.

A365543 counts partitions with subset-sum k, complement A046663.

A365661 counts strict partitions with subset-sum k, complement A365663.

A366738 counts semi-sums of partitions, strict A366741.

Cf. A002033, A006827, A122768, A126796, A238628, A365923, A365924, A367095.

Programs

Mathematica

Table[Length[Select[IntegerPartitions[n], !UnsameQ@@Total/@Union[Subsets[#]]&]], {n,0,15}]

Formula

a(n) = A000041(n) - A108917(n).