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

Links

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

Formula

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

Example

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).

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}]

Prog

(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

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.

Sequence in context: A145933 A300788 A120171 * A145816 A347610 A027583

Adjacent sequences: A364912 A364913 A364914 * A364916 A364917 A364918

Keyword

nonn

Author

Gus Wiseman, Aug 22 2023

Extensions

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

Status

approved