5
$\begingroup$

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$.]

$\endgroup$
  • $\begingroup$ Until I read non increasing, I thought a partition could start (1,2,3,...), and a subpartition would be coordinate wise majorized by the partition (while being increasing until it hit zero terms. Is it important to consider and count this narrower subclass (left subs), or do you really want your class (right subs)? Gerhard "Likes Going Southwest To Northeast" Paseman, 2017.09.16. $\endgroup$ – Gerhard Paseman Sep 16 '17 at 20:01
  • $\begingroup$ I don't think I understand your comment yet.... $\endgroup$ – Greg Martin Sep 19 '17 at 7:34
  • $\begingroup$ Suppose we consider the partition (3,1,1). I will write it as (1,1,3) to agree with the concepts above. You would count (1,2) as a subpartition but I would say it is a right sub. We would both count (1,1,2) as it is both a left and a right sub. The left subs are (1), and 4 of the form (1,1,x). (I write (1,1) as (1,1,0) temporarily.) The right subs also include (1,x) for x = 2 and 3. My question is: do you want to consider the narrower class of left subs? Gerhard "It's How You Write It" Paseman, 2017.09.19. $\endgroup$ – Gerhard Paseman Sep 19 '17 at 21:56
  • $\begingroup$ Thanks, I understand now! Answer: I really want my class, right subs in your terminology. $\endgroup$ – Greg Martin Sep 19 '17 at 23:20
  • 1
    $\begingroup$ I have added the OEIS sequence oeis.org/A297626 consisting of the partitions having the most subpartitions. This elaborates on oeis.org/A116480, the maximal number of subpartitions, in the same way that oeis.org/A117500 relates to oeis.org/A003040 (related to standard Young tableaux rather than subpartitions). The new sequence includes a link back to this mathoverflow page. $\endgroup$ – Brian Hopkins Jan 28 '18 at 20:06
9
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would certainly be interested in a concrete upper bound that could be derived via this approach. $\endgroup$ – Greg Martin Sep 19 '17 at 7:38

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.