A074658 Number of 'convex' partitions of n; i.e., partitions of n for which the Ferrers graph is the intersection of a convex set and the integer lattice.

1, 1, 2, 3, 5, 6, 9, 12, 13, 17, 23, 25, 30, 37, 38, 48, 61, 61, 67, 85, 89, 105, 120, 122, 138, 163, 174, 193, 216, 231, 252, 289, 289, 324, 369, 389, 428, 477, 481, 519, 587, 628, 661, 729, 760, 827, 902, 940, 999, 1095, 1140, 1238, 1337, 1380, 1464, 1616

Offset

0,3

Comments

Equivalently, a partition n = a_1 + ... + a_m with a_1 >= ... >= a_m >= 1 is convex if a_j >= floor(a_i + (a_k - a_i)*(j-i)/(k-i)) whenever 1 <= i < j < k <= m.

Can anyone supply a generating function or asymptotic formula?

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..500

Sergi Elizalde and Alejandro B. Galván, Triangular partitions: enumeration, structure, and generation, arXiv:2312.16353 [math.CO], 2023. Mentions this sequence.

Eric Weisstein's World of Mathematics, Ferrers Diagram.

Example

The only partition of 5 which is not convex is 5 = 3 + 1 + 1, so a(5) = A000041(5) - 1 = 6.

Mathematica

f[1, 1, 0, 0]=1; f[n_, m_, r_, s_] := Module[{nn, rr, ss}, If[GCD[r, s]!=1||2r*n>(m+1)(2r+s*m)||(nn=n-m*s+(r+1)(s-1)/2)<m-r, 0, f[n, m, r, s]=Sum[If[s*rr>=r*ss, f[nn, m-r, rr, ss], 0], {rr, 0, m-r-1}, {ss, 0, nn-m+r}]]]; a[n_] := Module[{r, s}, If[n<=1, 1, Sum[f[n, m, r, s], {m, 1, n}, {r, 0, m-1}, {s, 0, n-m}]]] (* f[n, m, r, s] = number of convex partitions of n into m parts, with bottom slope of convex hull equal to r/s *)

Crossrefs

The first and second differences are in A074659 and A074660.

Cf. A000041.

Sequence in context: A032718 A366143 A086191 * A186106 A329161 A124866

Adjacent sequences: A074655 A074656 A074657 * A074659 A074660 A074661

Keyword

nonn

Author

Dean Hickerson, Aug 29 2002

Status

approved