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

0, 0, 1, 1, 4, 3, 9, 7, 15, 16, 29, 23, 47, 43, 74, 65, 114, 100, 174, 153, 257, 228, 368, 312, 530, 454, 736, 645, 1025, 902, 1402, 1184, 1909, 1626, 2618, 2184, 3412, 2895, 4551, 3887, 5966, 5055, 7796, 6509, 10244, 8462, 13060, 10881, 16834, 14021, 21471

Offset: 1

Author

Gus Wiseman, Sep 12 2023

Keywords

• nonn

Examples

			The partition y = (3,3,2) has distinct parts {2,3}, and we have 9 = 3*2 + 1*3, so y is not counted under a(9).
The a(3) = 1 through a(10) = 16 partitions:
  (2)  (3)  (2)    (4)    (2)      (3)    (2)        (3)
            (3)    (5)    (3)      (5)    (4)        (4)
            (4)    (3,2)  (4)      (6)    (5)        (6)
            (2,2)         (5)      (7)    (6)        (7)
                          (6)      (3,3)  (7)        (8)
                          (2,2)    (4,3)  (8)        (9)
                          (3,3)    (5,2)  (2,2)      (3,3)
                          (4,2)           (4,2)      (4,4)
                          (2,2,2)         (4,3)      (5,2)
                                          (4,4)      (5,3)
                                          (5,3)      (5,4)
                                          (6,2)      (6,3)
                                          (2,2,2)    (7,2)
                                          (4,2,2)    (3,3,3)
                                          (2,2,2,2)  (4,3,2)
                                                     (5,2,2)
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..95

Crossrefs

Complement for subsets: A088314 or A365042, nonnegative A365073 or A365542.

For strict partitions we have A088528, nonnegative coefficients A365312.

For length-2 subsets we have A365321 (we use n instead of n-1).

For subsets we have A365322 or A365045, nonnegative coefficients A365380.

For nonnegative coefficients we have A365378, complement A365379.

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

combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Join@@IntegerPartitions/@Range[n-1],combp[n,Union[#]]=={}&]],{n,10}]

Python

from sympy.utilities.iterables import partitions
def A365323(n):
    a = {tuple(sorted(set(p))) for p in partitions(n)}
    return sum(1 for k in range(1,n) for d in partitions(k) if tuple(sorted(set(d))) not in a) # Chai Wah Wu, Sep 12 2023

Extensions

a(21)-a(51) from Chai Wah Wu, Sep 12 2023