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

%I #15 Sep 13 2023 14:16:22

%S 0,0,0,1,1,4,2,9,5,13,10,28,7,45,25,51,32,101,31,148,50,166,106,291,

%T 47,374,176,450,179,721,121,963,285,1080,474,1534,200,2140,712,2407,

%U 599,3539,481,4546,1014,4885

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

%e The partition (5,2,2) has distinct parts {2,5} and has 11 = 3*2 + 1*5, so is not counted under a(11).

%e The partition (4,2,2) cannot be linearly combined to obtain 9, so is counted under a(9).

%e The partition (4,2,2) has distinct parts {2,4} and has 10 = 5*2 + 0*4, so is not counted under a(10).

%e The a(3) = 1 through a(10) = 10 partitions:

%e (2) (3) (2) (4) (2) (3) (2) (3)

%e (3) (5) (3) (5) (4) (4)

%e (4) (4) (6) (5) (6)

%e (22) (5) (7) (6) (7)

%e (6) (33) (7) (8)

%e (22) (8) (9)

%e (33) (22) (33)

%e (42) (42) (44)

%e (222) (44) (63)

%e (62) (333)

%e (222)

%e (422)

%e (2222)

%t combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];

%t Table[Length[Select[Join@@IntegerPartitions/@Range[n-1],combs[n,Union[#]]=={}&]],{n,0,10}]

%o (Python)

%o from sympy.utilities.iterables import partitions

%o def A365378(n):

%o a = {tuple(sorted(set(p))) for p in partitions(n)}

%o 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

%Y The complement for subsets is A365073, positive coefficients A088314.

%Y For strict partitions we have A365312, positive coefficients A088528.

%Y For positive coefficients we have A365323.

%Y The complement is counted by A365379.

%Y The version for subsets is A365380, positive coefficients A365322.

%Y The relatively prime case is A365382.

%Y A000041 counts integer partitions, strict A000009.

%Y A008284 counts partitions by length, strict A008289.

%Y A116861 and A364916 count linear combinations of strict partitions.

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

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

%Y Cf. A237668, A363225, A364272, A364345, A364914, A365320.

%K nonn,more

%O 0,6

%A _Gus Wiseman_, Sep 04 2023

%E a(21)-a(45) from _Chai Wah Wu_, Sep 13 2023