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

0, 0, 0, 1, 1, 4, 2, 9, 5, 13, 10, 28, 7, 45, 25, 51, 32, 101, 31, 148, 50, 166, 106, 291, 47, 374, 176, 450, 179, 721, 121, 963, 285, 1080, 474, 1534, 200, 2140, 712, 2407, 599, 3539, 481, 4546, 1014, 4885

Offset

0,6

Links

Table of n, a(n) for n=0..45.

Example

The partition (5,2,2) has distinct parts {2,5} and has 11 = 3*2 + 1*5, so is not counted under a(11).
The partition (4,2,2) cannot be linearly combined to obtain 9, so is counted under a(9).
The partition (4,2,2) has distinct parts {2,4} and has 10 = 5*2 + 0*4, so is not counted under a(10).
The a(3) = 1 through a(10) = 10 partitions:
  (2)  (3)  (2)   (4)  (2)    (3)   (2)     (3)
            (3)   (5)  (3)    (5)   (4)     (4)
            (4)        (4)    (6)   (5)     (6)
            (22)       (5)    (7)   (6)     (7)
                       (6)    (33)  (7)     (8)
                       (22)         (8)     (9)
                       (33)         (22)    (33)
                       (42)         (42)    (44)
                       (222)        (44)    (63)
                                    (62)    (333)
                                    (222)
                                    (422)
                                    (2222)

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@@IntegerPartitions/@Range[n-1], combs[n, Union[#]]=={}&]], {n, 0, 10}]

Prog

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

Crossrefs

The complement for subsets is A365073, positive coefficients A088314.

For strict partitions we have A365312, positive coefficients A088528.

For positive coefficients we have A365323.

The complement is counted by A365379.

The version for subsets is A365380, positive coefficients A365322.

The relatively prime case is A365382.

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.

Sequence in context: A191663 A206561 A008831 * A289506 A373710 A363268

Adjacent sequences: A365375 A365376 A365377 * A365379 A365380 A365381

Keyword

nonn,more

Author

Gus Wiseman, Sep 04 2023

Extensions

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

Status

approved