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

Author

Gus Wiseman, Aug 31 2023

Keywords

• nonn

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.

Examples

			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)
		

Links

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

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.

Programs

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

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

Extensions

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