A364350 Number of strict integer partitions of n such that no part can be written as a nonnegative linear combination of the others.

1, 1, 1, 1, 1, 2, 1, 3, 2, 3, 3, 5, 3, 6, 5, 7, 6, 9, 7, 11, 10, 14, 12, 16, 15, 20, 17, 24, 22, 27, 29, 32, 30, 41, 36, 49, 45, 50, 52, 65, 63, 70, 77, 80, 83, 104, 98, 107, 116, 126, 134, 152, 148, 162, 180, 196, 195, 227, 227, 238, 272, 271, 293, 333, 325

Offset: 0

Author

Gus Wiseman, Aug 15 2023

Keywords

• nonn

Comments

A way of writing n as a (presumed nonnegative) linear combination of a finite sequence y is any sequence of pairs (k_i,y_i) such that k_i >= 0 and Sum k_i*y_i = n. For example, the pairs ((3,1),(1,1),(1,1),(0,2)) are a way of writing 5 as a linear combination of (1,1,1,2), namely 5 = 3*1 + 1*1 + 1*1 + 0*2. Of course, there are A000041(n) ways to write n as a linear combination of (1..n).

Examples

			The a(16) = 6 through a(22) = 12 strict partitions:
  (16)     (17)     (18)     (19)     (20)      (21)      (22)
  (9,7)    (9,8)    (10,8)   (10,9)   (11,9)    (12,9)    (13,9)
  (10,6)   (10,7)   (11,7)   (11,8)   (12,8)    (13,8)    (14,8)
  (11,5)   (11,6)   (13,5)   (12,7)   (13,7)    (15,6)    (15,7)
  (13,3)   (12,5)   (14,4)   (13,6)   (14,6)    (16,5)    (16,6)
  (7,5,4)  (13,4)   (7,6,5)  (14,5)   (17,3)    (17,4)    (17,5)
           (14,3)   (8,7,3)  (15,4)   (8,7,5)   (19,2)    (18,4)
           (15,2)            (16,3)   (9,6,5)   (11,10)   (19,3)
           (7,6,4)           (17,2)   (9,7,4)   (8,7,6)   (12,10)
                             (8,6,5)  (11,5,4)  (9,7,5)   (9,7,6)
                             (9,6,4)            (10,7,4)  (9,8,5)
                                                (10,8,3)  (7,6,5,4)
                                                (11,6,4)
                                                (11,7,3)
		

Crossrefs

For sums of subsets instead of combinations of partitions we have A151897.

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

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

The complement in strict partitions is A364839, non-strict A364913.

A more strict variation is A364915.

The case of all positive coefficients is A365006.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A108917 counts knapsack partitions, ranks A299702.

A116861 and A364916 count linear combinations of strict partitions.

A323092 (ranks A320340) and A120641 count double-free partitions.

A364912 counts linear combinations of partitions of k.

Cf. A007865, A085489, A237113, A275972, A363226, A364272, A364533, A364910, A364911, A365002, A365004.

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

Python

from sympy.utilities.iterables import partitions
def A364350(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):
        if max(p.values(),default=0)==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

Extensions

More terms and offset corrected by Martin Fuller, Sep 11 2023