login
Number of strict integer partitions of n such that no part can be written as a nonnegative linear combination of the others.
81

%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