A365072 - OEIS

%I #14 Sep 20 2023 18:12:33

%S 1,1,2,2,3,3,4,5,6,8,9,17,15,31,34,53,65,109,117,196,224,328,405,586,

%T 673,968,1163,1555,1889,2531,2986,3969,4744,6073,7333,9317,11053,

%U 14011,16710,20702,24714,30549,36127,44413,52561,63786,75583,91377,107436,129463

%N Number of integer partitions of n such that no distinct part can be written as a (strictly) positive linear combination of the other distinct parts.

%C We consider (for example) that 2x + y + 3z is a positive linear combination of (x,y,z), but 2x + y is not, as the coefficient of z is 0.

%e The a(1) = 1 through a(8) = 6 partitions:

%e   (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)

%e        (11)  (111)  (22)    (32)     (33)      (43)       (44)

%e                     (1111)  (11111)  (222)     (52)       (53)

%e                                      (111111)  (322)      (332)

%e                                                (1111111)  (2222)

%e                                                           (11111111)

%e The a(11) = 17 partitions:

%e   (11)  (9,2)  (7,2,2)  (5,3,2,1)  (4,3,2,1,1)  (1,1,1,1,1,1,1,1,1,1,1)

%e         (8,3)  (6,3,2)  (5,2,2,2)  (3,2,2,2,2)

%e         (7,4)  (5,4,2)  (4,3,2,2)

%e         (6,5)  (5,3,3)  (3,3,3,2)

%e                (4,4,3)

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

%t Table[Length[Select[Union/@IntegerPartitions[n], Function[ptn,!Or@@Table[combp[ptn[[k]],Delete[ptn,k]]!={}, {k,Length[ptn]}]]@*Union]],{n,0,15}]

%o (Python)

%o from sympy.utilities.iterables import partitions

%o def A365072(n):

%o     if n <= 1: return 1

%o     alist = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)]

%o     c = 1

%o     for p in partitions(n,k=n-1):

%o         s = set(p)

%o         for q in s:

%o             if tuple(sorted(s-{q})) in alist[q]:

%o                 break

%o         else:

%o             c += 1

%o     return c # _Chai Wah Wu_, Sep 20 2023

%Y The nonnegative version is A364915, strict A364350.

%Y The strict case is A365006.

%Y For subsets instead of partitions we have A365044, complement A365043.

%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 A237667 counts sum-free partitions, binary A236912.

%Y A364912 counts positive linear combinations of partitions.

%Y A365068 counts combination-full partitions, strict A364839.

%Y Cf. A085489, A108917, A151897, A325862, A364272, A364910, A364911, A364913.

%K nonn

%O 0,3

%A _Gus Wiseman_, Aug 31 2023

%E a(31)-a(49) from _Chai Wah Wu_, Sep 20 2023