Upper bound for number of subpartitions of a partition

Question

Let $\alpha = (\alpha_1,\alpha_2,\dots)$ be a partition of the positive integer $n$, that is, a nonincreasing sequence of nonnegative integers $\alpha_j$, with only finitely many nonzero terms, whose sum is $n$. A subpartition of $\alpha$ is a partition $\beta = (\beta_1,\beta_2,\dots)$ such that $\beta_j \le \alpha_j$ for all $j\ge1$. How many distinct subpartitions can $\alpha$ have? I am interested in as good an upper bound as possible, in terms of $n$, that holds for every partition of $n$ (that is, I'm interested in bounds that hold in the "worst case").

Every subpartition of $\alpha$ is a partition of some number $0\le m\le n$, and so a trivial upper bound (using the notation $p(m)$ for the number of partitions of $m$) is $$ \sum_{m=0}^n p(m) \le (n+1)p(n) \ll e^{\pi\sqrt{2n/3}} $$ by the Hardy–Ramanujan asymptotics for $p(n)$. However, I suspect the truth is quite a bit smaller than this. References to existing bounds would be optimal, but arguments that improve this trivial bound substantially (including improvements to the constant in the exponent) are very welcome.

[Note that we are literally counting partitions here, not weighting the partitions differently according to their shape. (The motivation for my question comes from trying to estimate the number of isomorphism classes of subgroups of a finite $p$-group.) Asking a similar question but where partitions are weighted by a Plancherel measure, while not relevant to this question, is probably still interesting (and, as far as I know, an open problem); there my suspicion is that this upper bound cannot be substantially improved—the intuition being that "typical" partitions $\alpha$ of $n$ give the worst case for the upper bound, and most typical partitions of $(1-\epsilon)n$ might in fact be subpartitions of $\alpha$.]

Answer 1

Some data suggests that the partition(s) of $n$ maximizing the number of subpartitions has the same limiting curve as for the the partition(s) of $n$ maximizing the number of standard Young tableaux of that shape. This is the famous curve of Logan-Shepp and Vershik-Kerov given parametrically by $$ x = y + 2\cos\theta $$ $$ y = \frac{2}{\pi}(\sin\theta-\theta\cos\theta), $$ for $0\leq\theta\leq \pi$. See for instance Section 3 of https://arxiv.org/pdf/math/0512035.pdf. For instance, when $n=45$ there are two conjugate partitions $\lambda$ that maximize the number of subpartitions. One is $(11,8,6,5,4,3,2,2,1,1,1,1)$. There are also two conjugate partitions maximizing the number of SYT, one being $(11,8,6,5,4,3,3,2,2,1,1)$.

Answer 2

Here's the outline of an answer; I can work on details if it seems promising.

The exact count of subpartitions of a given partition was given by MacMahon and can also be worked out as an application of the Gessel--Viennot lemma; see my answers to https://math.stackexchange.com/questions/146933/number-of-partitions-contained-within-young-shape-lambda.

The question then becomes which partition of $n$ has the most subpartitions. My intuition is the "most triangular" one (i.e., $(k, k-1, \dots, 2, 1)$ if $n$ is a triangular number, $(k, \dots, j+1, j-1, \dots, 1)$ if not).

Then you're better at the analytics than I am, Greg.

---

My hunch was off. Looking at just triangular numbers $n$, by 15 the triangular partition is not the one with the most subpartitions: $(5,4,3,2,1)$ has 132 while $(6,3,2,2,1,1)$ has 145. For other $n$, the nearly-triangular partitions are overtaken already at 9: $(5,2,1,1)$ has 33 subpartitions while a maximal nearly-triangular partition $(4,2,2,1)$ has 32.

By the way, the hunch would have been nice for triangular $n$ since the number of subpartitions of $(n, n-1, \dots, 2, 1)$ is the $n$th Catalan number.

It would be interesting to characterize the partitions with the most subpartitions. It seems these "fullest" partitions are more concave, with longer initial rows / left columns in the Ferrers's diagrams. But that's getting away from Greg's original problem.