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

0, 0, 0, 0, 1, 1, 5, 5, 12, 18, 30, 36, 65, 83, 120, 159, 225, 284, 395, 495, 665, 848, 1094, 1348, 1757, 2184, 2746, 3399, 4250, 5199, 6469, 7867, 9667, 11756, 14310, 17266, 20988, 25216, 30372, 36371, 43648, 52041, 62187, 73866, 87837, 104105, 123279, 145453

Offset: 1

Author

Richard Peterson, Oct 08 2020

Keywords

• nonn

Comments

In George Andrews’s partition notation, exponents mean repeated addition, not repeated multiplication. So (p^K)(q^L) with p0 and the parts pk arranged in increasing order, suppose E1p1+E2p2+..Ekpk>p(k+1) for some 1

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

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

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.

Examples

			(4^2)(7^3), a partition of 29, is in S(29) since 2*4=8>7.
Also, (1^3)(3^2)(7^1)(20^4), a partition of 96, is in S(96) since 3*1+2*3=9>7.
But (1^3)(4^5) is not in S(23) because 3*1 is not greater than 4.
		

Programs

Mathematica

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];
a[n_] := a[n] = Module[{c = 0}, Do[ c += ispart[p], {p, Reverse /@ IntegerPartitions[n]}]; c];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 50}] (* Jean-François Alcover, Nov 13 2020, after Andrew Howroyd *)

PARI

ispart(p)={my(s=0);for(i=1, #p, if(s>p[i]&&p[i]>p[i-1], return(1)); s+=p[i]);0}
a(n)={my(c=0); forpart(p=n, c+=ispart(p)); c} \\ Andrew Howroyd, Oct 25 2020

PARI

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

Extensions

Terms a(15) and beyond from Andrew Howroyd, Nov 03 2020

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.