A365379 Number of integer partitions with sum <= n whose distinct parts can be linearly combined using nonnegative coefficients to obtain n.

0, 1, 3, 5, 10, 14, 27, 35, 61, 83, 128, 166, 264, 327, 482, 632, 882, 1110, 1565, 1938, 2663, 3339, 4401, 5471, 7290, 8921, 11555, 14291, 18280, 22303, 28507, 34507, 43534, 52882, 65798, 79621, 98932, 118629, 146072, 175562, 214708, 256351, 312583, 371779

Offset: 0

Author

Gus Wiseman, Sep 04 2023

Keywords

• nonn

Examples

			The partition (4,2,2) cannot be linearly combined to obtain 9, so is not counted under a(9). On the other hand, the same partition (4,2,2) has distinct parts {2,4} and has 10 = 1*2 + 2*4, so is counted under a(10).
The a(1) = 1 through a(5) = 14 partitions:
  (1)  (1)   (1)    (1)     (1)
       (2)   (3)    (2)     (5)
       (11)  (11)   (4)     (11)
             (21)   (11)    (21)
             (111)  (21)    (31)
                    (22)    (32)
                    (31)    (41)
                    (111)   (111)
                    (211)   (211)
                    (1111)  (221)
                            (311)
                            (1111)
                            (2111)
                            (11111)
		

Crossrefs

For subsets with positive coefficients we have A088314, complement A088528.

The case of strict partitions with positive coefficients is also A088314.

The version for subsets is A365073, complement A365380.

The case of strict partitions is A365311, complement A365312.

The complement is counted by A365378.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A116861 and A364916 count linear combinations of strict partitions.

A364350 counts combination-free strict partitions, non-strict A364915.

A364839 counts combination-full strict partitions, non-strict A364913.

Cf. A237668, A363225, A364272, A364345, A364914, A365320, A365382.

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[Join@@Array[IntegerPartitions,n],combs[n,Union[#]]!={}&]],{n,0,10}]

Python

from sympy.utilities.iterables import partitions
def A365379(n):
    a = {tuple(sorted(set(p))) for p in partitions(n)}
    return sum(1 for m in range(1,n+1) for b in partitions(m) if any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023

Extensions

a(21)-a(43) from Chai Wah Wu, Sep 13 2023