A364349 Number of strict integer partitions of n containing the sum of no subset of the parts.

1, 1, 1, 2, 2, 3, 3, 5, 5, 8, 7, 11, 11, 15, 14, 21, 21, 28, 29, 38, 38, 51, 50, 65, 68, 82, 83, 108, 106, 130, 136, 163, 168, 206, 210, 248, 266, 307, 322, 381, 391, 457, 490, 553, 582, 675, 703, 797, 854, 952, 1000, 1147, 1187, 1331, 1437, 1564, 1656, 1869

Offset

0,4

Comments

First differs from A275972 in counting (7,5,3,1), which is not knapsack.

Links

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

Example

The partition y = (7,5,3,1) has no subset with sum in y, so is counted under a(16).
The partition y = (15,8,4,2,1) has subset {1,2,4,8} with sum in y, so is not counted under a(31).
The a(1) = 1 through a(9) = 8 partitions:
  (1)  (2)  (3)    (4)    (5)    (6)    (7)      (8)      (9)
            (2,1)  (3,1)  (3,2)  (4,2)  (4,3)    (5,3)    (5,4)
                          (4,1)  (5,1)  (5,2)    (6,2)    (6,3)
                                        (6,1)    (7,1)    (7,2)
                                        (4,2,1)  (5,2,1)  (8,1)
                                                          (4,3,2)
                                                          (5,3,1)
                                                          (6,2,1)

Mathematica

Table[Length[Select[IntegerPartitions[n], Function[ptn, UnsameQ@@ptn&&Select[Subsets[ptn, {2, Length[ptn]}], MemberQ[ptn, Total[#]]&]=={}]]], {n, 0, 30}]

Crossrefs

For subsets of {1..n} we have A151897, complement A364534.

The non-strict version is A237667, ranked by A364531.

The complement in strict partitions is counted by A364272.

The linear combination-free version is A364350.

The binary version is A364533, allowing re-used parts A364346.

A000041 counts partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A108917 counts knapsack partitions, strict A275972.

A236912 counts sum-free partitions (not re-using parts), complement A237113.

A323092 counts double-free partitions, ranks A320340.

Cf. A007865, A025065, A085489, A093971, A111133, A240861, A320347, A325862, A363226, A364345.

Sequence in context: A116575 A244800 A275972 * A364533 A090492 A325768

Adjacent sequences: A364346 A364347 A364348 * A364350 A364351 A364352

Keyword

nonn

Author

Gus Wiseman, Jul 29 2023

Status

approved