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

0, 0, 0, 1, 1, 1, 3, 2, 4, 5, 7, 7, 12, 12, 17, 20, 26, 29, 39, 43, 54, 62, 77, 88, 107, 122, 148, 168, 200, 229, 267, 308, 360, 407, 476, 536, 623, 710, 812, 917, 1050, 1190, 1349, 1530, 1733, 1944, 2206, 2483, 2794, 3138, 3524

Offset: 0

Author

Gus Wiseman, Aug 19 2023

Keywords

• nonn

Examples

			For y = (4,3,2) we can write 4 = 0*3 + 2*2, so y is counted under a(9).
For y = (11,5,3) we can write 11 = 1*5 + 2*3, so y is counted under a(19).
For y = (17,5,4,3) we can write 17 = 1*3 + 1*4 + 2*5, so y is counted under a(29).
The a(1) = 0 through a(12) = 12 strict partitions (A = 10, B = 11):
  .  .  (21)  (31)  (41)  (42)   (61)   (62)   (63)   (82)    (A1)    (84)
                          (51)   (421)  (71)   (81)   (91)    (542)   (93)
                          (321)         (431)  (432)  (532)   (632)   (A2)
                                        (521)  (531)  (541)   (641)   (B1)
                                               (621)  (631)   (731)   (642)
                                                      (721)   (821)   (651)
                                                      (4321)  (5321)  (732)
                                                                      (741)
                                                                      (831)
                                                                      (921)
                                                                      (5421)
                                                                      (6321)
		

Crossrefs

For sums instead of combinations we have A364272, binary A364670.

The complement in strict partitions is A364350.

Non-strict versions are A364913 and the complement of A364915.

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

The case of no all positive coefficients is A365006.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A116861 and A364916 count linear combinations of strict partitions.

Cf. A085489, A151897, A236912, A237113, A237667, A275972, A363226, A365002.

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

Python

from sympy.utilities.iterables import partitions
def A364839(n):
    if n <= 1: return 0
    alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 0
    for p in partitions(n,k=n-1):
        if max(p.values(),default=0)==1:
            s = set(p)
            if 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