A365072 Number of integer partitions of n such that no distinct part can be written as a (strictly) positive linear combination of the other distinct parts.

1, 1, 2, 2, 3, 3, 4, 5, 6, 8, 9, 17, 15, 31, 34, 53, 65, 109, 117, 196, 224, 328, 405, 586, 673, 968, 1163, 1555, 1889, 2531, 2986, 3969, 4744, 6073, 7333, 9317, 11053, 14011, 16710, 20702, 24714, 30549, 36127, 44413, 52561, 63786, 75583, 91377, 107436, 129463

Offset

0,3

Comments

We consider (for example) that 2x + y + 3z is a positive linear combination of (x,y,z), but 2x + y is not, as the coefficient of z is 0.

Links

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

Example

The a(1) = 1 through a(8) = 6 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (111)  (22)    (32)     (33)      (43)       (44)
                    (1111)  (11111)  (222)     (52)       (53)
                                     (111111)  (322)      (332)
                                               (1111111)  (2222)
                                                          (11111111)
The a(11) = 17 partitions:
  (11)  (9,2)  (7,2,2)  (5,3,2,1)  (4,3,2,1,1)  (1,1,1,1,1,1,1,1,1,1,1)
        (8,3)  (6,3,2)  (5,2,2,2)  (3,2,2,2,2)
        (7,4)  (5,4,2)  (4,3,2,2)
        (6,5)  (5,3,3)  (3,3,3,2)
               (4,4,3)

Mathematica

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

Prog

(Python)
from sympy.utilities.iterables import partitions
def A365072(n):
    if n <= 1: return 1
    alist = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)]
    c = 1
    for p in partitions(n, k=n-1):
        s = set(p)
        for q in s:
            if tuple(sorted(s-{q})) in alist[q]:
                break
        else:
            c += 1
    return c # Chai Wah Wu, Sep 20 2023

Crossrefs

The nonnegative version is A364915, strict A364350.

The strict case is A365006.

For subsets instead of partitions we have A365044, complement A365043.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A116861 and A364916 count linear combinations of strict partitions.

A237667 counts sum-free partitions, binary A236912.

A364912 counts positive linear combinations of partitions.

A365068 counts combination-full partitions, strict A364839.

Cf. A085489, A108917, A151897, A325862, A364272, A364910, A364911, A364913.

Sequence in context: A015753 A005686 A328675 * A118082 A120160 A017980

Adjacent sequences: A365069 A365070 A365071 * A365073 A365074 A365075

Keyword

nonn

Author

Gus Wiseman, Aug 31 2023

Extensions

a(31)-a(49) from Chai Wah Wu, Sep 20 2023

Status

approved