A365006 Number of strict integer partitions of n such that no part can be written as a (strictly) positive linear combination of the others.

1, 1, 1, 1, 1, 2, 1, 3, 2, 4, 4, 8, 4, 11, 9, 16, 14, 25, 20, 37, 31, 49, 47, 73, 64, 101, 96, 135, 133, 190, 181, 256, 253, 336, 342, 453, 452, 596, 609, 771, 803, 1014, 1041, 1309, 1362, 1674, 1760, 2151, 2249, 2736, 2884, 3449, 3661, 4366, 4615, 5486, 5825

Offset

0,6

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

Chai Wah Wu, Table of n, a(n) for n = 0..109

Example

The a(8) = 2 through a(13) = 11 partitions:
  (8)    (9)      (10)       (11)       (12)       (13)
  (5,3)  (5,4)    (6,4)      (6,5)      (7,5)      (7,6)
         (7,2)    (7,3)      (7,4)      (5,4,3)    (8,5)
         (4,3,2)  (4,3,2,1)  (8,3)      (5,4,2,1)  (9,4)
                             (9,2)                 (10,3)
                             (5,4,2)               (11,2)
                             (6,3,2)               (6,4,3)
                             (5,3,2,1)             (6,5,2)
                                                   (7,4,2)
                                                   (5,4,3,1)
                                                   (6,4,2,1)

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[IntegerPartitions[n], UnsameQ@@#&&And@@Table[combp[#[[k]], Delete[#, k]]=={}, {k, Length[#]}]&]], {n, 0, 30}]

Prog

(Python)
from sympy.utilities.iterables import partitions
def A365006(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):
        if max(p.values()) == 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 for subsets appears to be A124506.

For sums instead of combinations we have A364349, binary A364533.

The nonnegative version is A364350, complement A364839.

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

The non-strict version is A365072, nonnegative A364915.

A000041 counts integer partitions, strict A000009.

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. A151897, A237113, A236912, A237667, A275972, A363226, A364272, A364913, A365004, A365068.

Sequence in context: A206738 A282971 A174618 * A144241 A094173 A214370

Adjacent sequences: A365003 A365004 A365005 * A365007 A365008 A365009

Keyword

nonn

Author

Gus Wiseman, Aug 31 2023

Extensions

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

Status

approved