cp's OEIS Frontend

A364915 Number of integer partitions of n such that no distinct part can be written as a nonnegative linear combination of other distinct parts.

%I A364915 #22 Sep 25 2023 18:22:18
%S A364915 1,1,2,2,3,3,4,5,6,7,8,12,10,16,16,19,21,29,25,37,35,44,46,60,55,75,
%T A364915 71,90,90,114,110,140,138,167,163,217,201,248,241,298,303,359,355,425,
%U A364915 422,520,496,594,603,715,706,834,826,968,972,1153,1147,1334,1315,1530
%N A364915 Number of integer partitions of n such that no distinct part can be written as a nonnegative linear combination of other distinct parts.
%F A364915 a(n) = A000041(n) - A365068(n).
%e A364915 The a(1) = 1 through a(10) = 8 partitions (A=10):
%e A364915   1  2   3    4     5      6       7        8         9          A
%e A364915      11  111  22    32     33      43       44        54         55
%e A364915               1111  11111  222     52       53        72         64
%e A364915                            111111  322      332       333        73
%e A364915                                    1111111  2222      522        433
%e A364915                                             11111111  3222       3322
%e A364915                                                       111111111  22222
%e A364915                                                                  1111111111
%e A364915 The partition (5,4,3) has no part that can be written as a nonnegative linear combination of the others, so is counted under a(12).
%e A364915 The partition (6,4,3,2) has 6=4+2, or 6=3+3, or 6=2+2+2, or 4=2+2, so is not counted under a(15).
%t A364915 combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
%t A364915 Table[Length[Select[IntegerPartitions[n], Function[ptn,!Or@@Table[combs[ptn[[k]],Delete[ptn,k]]!={}, {k,Length[ptn]}]]@*Union]], {n,0,15}]
%o A364915 (Python)
%o A364915 from sympy.utilities.iterables import partitions
%o A364915 def A364915(n):
%o A364915     if n <= 1: return 1
%o A364915     alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 1
%o A364915     for p in partitions(n,k=n-1):
%o A364915         s = set(p)
%o A364915         if not any(set(t).issubset(s-{q}) for q in s for t in alist[q]):
%o A364915             c += 1
%o A364915     return c # _Chai Wah Wu_, Sep 23 2023
%Y A364915 For sums instead of combinations we have A237667, binary A236912.
%Y A364915 For subsets instead of partitions we have A326083, complement A364914.
%Y A364915 The strict case is A364350.
%Y A364915 The complement is A365068, strict A364839.
%Y A364915 The positive case is A365072, strict A365006.
%Y A364915 A000041 counts integer partitions, strict A000009.
%Y A364915 A007865 counts binary sum-free sets w/ re-usable parts, complement A093971.
%Y A364915 A008284 counts partitions by length, strict A008289.
%Y A364915 A116861 and A364916 count linear combinations of strict partitions.
%Y A364915 A364912 counts linear combinations of partitions of k.
%Y A364915 Cf. A085489, A108917, A151897, A237113, A323092, A364272, A364533, A364910, A364911, A364913.
%K A364915 nonn
%O A364915 0,3
%A A364915 _Gus Wiseman_, Aug 22 2023
%E A364915 a(37)-a(59) from _Chai Wah Wu_, Sep 25 2023