A364915 Number of integer partitions of n such that no distinct part can be written as a nonnegative linear combination of other distinct parts.

1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 12, 10, 16, 16, 19, 21, 29, 25, 37, 35, 44, 46, 60, 55, 75, 71, 90, 90, 114, 110, 140, 138, 167, 163, 217, 201, 248, 241, 298, 303, 359, 355, 425, 422, 520, 496, 594, 603, 715, 706, 834, 826, 968, 972, 1153, 1147, 1334, 1315, 1530

Offset: 0

Author

Gus Wiseman, Aug 22 2023

Keywords

• nonn

Examples

			The a(1) = 1 through a(10) = 8 partitions (A=10):
  1  2   3    4     5      6       7        8         9          A
     11  111  22    32     33      43       44        54         55
              1111  11111  222     52       53        72         64
                           111111  322      332       333        73
                                   1111111  2222      522        433
                                            11111111  3222       3322
                                                      111111111  22222
                                                                 1111111111
The partition (5,4,3) has no part that can be written as a nonnegative linear combination of the others, so is counted under a(12).
The partition (6,4,3,2) has 6=4+2, or 6=3+3, or 6=2+2+2, or 4=2+2, so is not counted under a(15).
		

Crossrefs

For sums instead of combinations we have A237667, binary A236912.

For subsets instead of partitions we have A326083, complement A364914.

The strict case is A364350.

The complement is A365068, strict A364839.

The positive case is A365072, strict A365006.

A000041 counts integer partitions, strict A000009.

A007865 counts binary sum-free sets w/ re-usable parts, complement A093971.

A008284 counts partitions by length, strict A008289.

A116861 and A364916 count linear combinations of strict partitions.

A364912 counts linear combinations of partitions of k.

Cf. A085489, A108917, A151897, A237113, A323092, A364272, A364533, A364910, A364911, A364913.

Programs

Mathematica

combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[IntegerPartitions[n], Function[ptn,!Or@@Table[combs[ptn[[k]],Delete[ptn,k]]!={}, {k,Length[ptn]}]]@*Union]], {n,0,15}]

Python

from sympy.utilities.iterables import partitions
def A364915(n):
    if n <= 1: return 1
    alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 1
    for p in partitions(n,k=n-1):
        s = set(p)
        if not any(set(t).issubset(s-{q}) for q in s for t in alist[q]):
            c += 1
    return c # Chai Wah Wu, Sep 23 2023

Formula

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

Extensions

a(37)-a(59) from Chai Wah Wu, Sep 25 2023