login
Number of strict integer partitions of n such that no part can be written as a (strictly) positive linear combination of the others.
9

%I #19 Sep 20 2023 18:16:31

%S 1,1,1,1,1,2,1,3,2,4,4,8,4,11,9,16,14,25,20,37,31,49,47,73,64,101,96,

%T 135,133,190,181,256,253,336,342,453,452,596,609,771,803,1014,1041,

%U 1309,1362,1674,1760,2151,2249,2736,2884,3449,3661,4366,4615,5486,5825

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

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

%H Chai Wah Wu, <a href="/A365006/b365006.txt">Table of n, a(n) for n = 0..109</a>

%e The a(8) = 2 through a(13) = 11 partitions:

%e (8) (9) (10) (11) (12) (13)

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

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

%e (4,3,2) (4,3,2,1) (8,3) (5,4,2,1) (9,4)

%e (9,2) (10,3)

%e (5,4,2) (11,2)

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

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

%e (7,4,2)

%e (5,4,3,1)

%e (6,4,2,1)

%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[IntegerPartitions[n],UnsameQ@@#&&And@@Table[combp[#[[k]],Delete[#,k]]=={},{k,Length[#]}]&]],{n,0,30}]

%o (Python)

%o from sympy.utilities.iterables import partitions

%o def A365006(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 if max(p.values()) == 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 for subsets appears to be A124506.

%Y For sums instead of combinations we have A364349, binary A364533.

%Y The nonnegative version is A364350, complement A364839.

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

%Y The non-strict version is A365072, nonnegative A364915.

%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 A364912 counts linear combinations of partitions of k.

%Y Cf. A151897, A237113, A236912, A237667, A275972, A363226, A364272, A364913, A365004, A365068.

%K nonn

%O 0,6

%A _Gus Wiseman_, Aug 31 2023

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