|
%I #19 Sep 24 2023 04:16:25
%S 1,1,1,1,1,2,1,3,2,3,3,5,3,6,5,7,6,9,7,11,10,14,12,16,15,20,17,24,22,
%T 27,29,32,30,41,36,49,45,50,52,65,63,70,77,80,83,104,98,107,116,126,
%U 134,152,148,162,180,196,195,227,227,238,272,271,293,333,325
%N Number of strict integer partitions of n such that no part can be written as a nonnegative linear combination of the others.
%C A way of writing n as a (presumed nonnegative) linear combination of a finite sequence y is any sequence of pairs (k_i,y_i) such that k_i >= 0 and Sum k_i*y_i = n. For example, the pairs ((3,1),(1,1),(1,1),(0,2)) are a way of writing 5 as a linear combination of (1,1,1,2), namely 5 = 3*1 + 1*1 + 1*1 + 0*2. Of course, there are A000041(n) ways to write n as a linear combination of (1..n).
%e The a(16) = 6 through a(22) = 12 strict partitions:
%e (16) (17) (18) (19) (20) (21) (22)
%e (9,7) (9,8) (10,8) (10,9) (11,9) (12,9) (13,9)
%e (10,6) (10,7) (11,7) (11,8) (12,8) (13,8) (14,8)
%e (11,5) (11,6) (13,5) (12,7) (13,7) (15,6) (15,7)
%e (13,3) (12,5) (14,4) (13,6) (14,6) (16,5) (16,6)
%e (7,5,4) (13,4) (7,6,5) (14,5) (17,3) (17,4) (17,5)
%e (14,3) (8,7,3) (15,4) (8,7,5) (19,2) (18,4)
%e (15,2) (16,3) (9,6,5) (11,10) (19,3)
%e (7,6,4) (17,2) (9,7,4) (8,7,6) (12,10)
%e (8,6,5) (11,5,4) (9,7,5) (9,7,6)
%e (9,6,4) (10,7,4) (9,8,5)
%e (10,8,3) (7,6,5,4)
%e (11,6,4)
%e (11,7,3)
%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[IntegerPartitions[n],UnsameQ@@#&&And@@Table[combs[#[[k]],Delete[#,k]]=={},{k,Length[#]}]&]],{n,0,15}]
%o (Python)
%o from sympy.utilities.iterables import partitions
%o def A364350(n):
%o if n <= 1: return 1
%o alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 1
%o for p in partitions(n,k=n-1):
%o if max(p.values(),default=0)==1:
%o s = set(p)
%o if not any(set(t).issubset(s-{q}) for q in s for t in alist[q]):
%o c += 1
%o return c # _Chai Wah Wu_, Sep 23 2023
%Y For sums of subsets instead of combinations of partitions we have A151897.
%Y For sums instead of combinations we have A237667, binary A236912.
%Y For subsets instead of partitions we have A326083, complement A364914.
%Y The complement in strict partitions is A364839, non-strict A364913.
%Y A more strict variation is A364915.
%Y The case of all positive coefficients is A365006.
%Y A000041 counts integer partitions, strict A000009.
%Y A008284 counts partitions by length, strict A008289.
%Y A108917 counts knapsack partitions, ranks A299702.
%Y A116861 and A364916 count linear combinations of strict partitions.
%Y A323092 (ranks A320340) and A120641 count double-free partitions.
%Y A364912 counts linear combinations of partitions of k.
%Y Cf. A007865, A085489, A237113, A275972, A363226, A364272, A364533, A364910, A364911, A365002, A365004.
%K nonn
%O 0,6
%A _Gus Wiseman_, Aug 15 2023
%E More terms and offset corrected by _Martin Fuller_, Sep 11 2023
|
