A338085 - OEIS

%I #28 Nov 14 2020 07:06:39

%S 0,0,0,0,1,1,5,5,12,18,30,36,65,83,120,159,225,284,395,495,665,848,

%T 1094,1348,1757,2184,2746,3399,4250,5199,6469,7867,9667,11756,14310,

%U 17266,20988,25216,30372,36371,43648,52041,62187,73866,87837,104105,123279,145453

%N a(n) is the cardinality of S(n), the subset of partitions of n such that there are enough smaller parts to add together to be greater than a larger part.

%C In George Andrews’s partition notation, exponents mean repeated addition, not repeated multiplication. So (p^K)(q^L) with p<q denotes K parts of size p, combined with L parts of size q, thus a rectangle of width q and depth L atop another rectangle of width p and depth L in the Ferrers diagram. Given a partition Lambda(n)=(p1^E1)(p2^E2)...(pj^Ej) with all Ek>0 and the parts pk arranged in increasing order, suppose E1p1+E2p2+..Ekpk>p(k+1) for some 1<k<j. Then Lambda(n) is in S(n).

%C For any partition in S, the number of parts must be at least 3, with at least 2 distinct parts.

%C The sequence a(n) is nondecreasing since if a(n-1)=t, then t distinct elements of S(n) can be formed by putting a dot in the lower left corner of the Ferrers diagram for each element of S(n-1).

%C Closure: Given a partition X in S(x) and partition Y in S(y): The partition X+Y given by concatenation is in S(x+y). So a(x)+a(y) might be provably less than or equal to S(x+y). X and Y can be multiplied to give a partition XY in S(xy). The two operations obey distributivity of multiplication over addition.

%e (4^2)(7^3), a partition of 29, is in S(29) since 2*4=8>7.

%e Also, (1^3)(3^2)(7^1)(20^4), a partition of 96, is in S(96) since 3*1+2*3=9>7.

%e But (1^3)(4^5) is not in S(23) because 3*1 is not greater than 4.

%t ispart[p_] := Module[{s = 0}, For[i = 1, i <= Length[p], i++, If[s > p[[i]] && p[[i]] > p[[i-1]], Return[1]]; s += p[[i]]]; 0];

%t a[n_] := a[n] = Module[{c = 0}, Do[ c += ispart[p], {p, Reverse /@ IntegerPartitions[n]}]; c];

%t Table[Print[n, " ", a[n]]; a[n], {n, 1, 50}] (* _Jean-François Alcover_, Nov 13 2020, after _Andrew Howroyd_ *)

%o (PARI)

%o ispart(p)={my(s=0);for(i=1, #p, if(s>p[i]&&p[i]>p[i-1], return(1)); s+=p[i]);0}

%o a(n)={my(c=0); forpart(p=n, c+=ispart(p)); c} \\ _Andrew Howroyd_, Oct 25 2020

%o (PARI)

%o a(n)={local(Cache=Map()); my(F(r,k,b)=my(hk=[r,k,b],z); if(!mapisdefined(Cache, hk, &z), z = if(k<=1, b, sum(m=0, r\k, self()(r-m*k, k-1, b||(m&&r-m*k>k)))); mapput(Cache, hk, z)); z); F(n,n,0)} \\ _Andrew Howroyd_, Nov 03 2020

%K nonn

%O 1,7

%A _Richard Peterson_, Oct 08 2020

%E Terms a(15) and beyond from _Andrew Howroyd_, Nov 03 2020