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

%I #14 Oct 24 2023 10:46:11

%S 0,0,0,1,1,1,3,2,4,5,7,7,12,12,17,20,26,29,39,43,54,62,77,88,107,122,

%T 148,168,200,229,267,308,360,407,476,536,623,710,812,917,1050,1190,

%U 1349,1530,1733,1944,2206,2483,2794,3138,3524

%N Number of strict integer partitions of n such that some part can be written as a nonnegative linear combination of the others.

%e For y = (4,3,2) we can write 4 = 0*3 + 2*2, so y is counted under a(9).

%e For y = (11,5,3) we can write 11 = 1*5 + 2*3, so y is counted under a(19).

%e For y = (17,5,4,3) we can write 17 = 1*3 + 1*4 + 2*5, so y is counted under a(29).

%e The a(1) = 0 through a(12) = 12 strict partitions (A = 10, B = 11):

%e . . (21) (31) (41) (42) (61) (62) (63) (82) (A1) (84)

%e (51) (421) (71) (81) (91) (542) (93)

%e (321) (431) (432) (532) (632) (A2)

%e (521) (531) (541) (641) (B1)

%e (621) (631) (731) (642)

%e (721) (821) (651)

%e (4321) (5321) (732)

%e (741)

%e (831)

%e (921)

%e (5421)

%e (6321)

%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@@#&&Or@@Table[combs[#[[k]], Delete[#,k]]!={}, {k,Length[#]}]&]],{n,0,15}]

%o (Python)

%o from sympy.utilities.iterables import partitions

%o def A364839(n):

%o if n <= 1: return 0

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

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

%o if max(p.values(),default=0)==1:

%o s = set(p)

%o if 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 instead of combinations we have A364272, binary A364670.

%Y The complement in strict partitions is A364350.

%Y Non-strict versions are A364913 and the complement of A364915.

%Y For subsets instead of partitions we have A364914, complement A326083.

%Y The case of no all positive coefficients is A365006.

%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 Cf. A085489, A151897, A236912, A237113, A237667, A275972, A363226, A365002.

%K nonn

%O 0,7

%A _Gus Wiseman_, Aug 19 2023