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

Comments

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

Links

Table of n, a(n) for n=0..49.

Formula

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

Example

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)

Mathematica

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

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.

Sequence in context: A058596 A180964 A237668 * A209423 A357620 A185784

Adjacent sequences: A366751 A366752 A366753 * A366755 A366756 A366757

Keyword

nonn

Author

Gus Wiseman, Nov 08 2023

Status

approved