Length of the longest chain in dominance order

Question

If $\Pi_n$ is the set of partitions of $n$, then for $\lambda, \mu\in \Pi_n$ we say $\mu$ dominates $\lambda$ if $\sum\limits_{i=1}^k \lambda_i \leq \sum\limits_{i=1}^k \mu_i$ for all $k$. This gives a partial order on $\Pi_n$ which is not a total order if $n>5$. For example, $(4,1,1)$ and $(3,3)$ are not comparable in $\Pi_6$. This is closely related to the usual ordering on dominant weights in Lie theory.

Question 1: What is the length of a maximal chain in the dominance order on $\Pi_n$? Given the Young diagram for $\lambda$, we get something smaller in the dominance order by moving one square down and to the left in such a way that we get another Young diagram (i.e. applying a simple lowering operator). So this is asking for a longest such "path" from the horizontal Young diagram $(n,0,\ldots,0)\in \Pi_n$ to the vertical Young diagram $(1,1,\ldots, 1,1)\in \Pi_n$.

Question 2: Is there a formula for the number of maximal chains?

Answer 1

The longest (descending) chain starts obviously with the partition $n$ having a unique part and ends with the partition $1+1+\dots+1$ into singletons. One should move from $n$ to $1+\dots+1$ by moving dots (unities) down row by row whenever possible along staircases: \begin{eqnarray*}&&n,(n-1)+1,(n-2)+2,(n-2)+1+1,(n-3)+2+1,(n-4)+3+1,\\&&(n-4)+2+2,(n-4)+2+1+1,(n-5)+3+1+1,(n-5)+2+2+1,\\&&(n-6)+3+2+1,(n-7)+4+2+1,\dots\end{eqnarray*} etc. Rule: $\dots+\lambda_k+\lambda_{k+1}+\dots$ moves to $\dots+(\lambda_{k}-1)+ (\lambda_{k+1}+1)+\dots$ if $k$ is the largest index such that $\lambda_{k+1}-\lambda_k\geq 2$ (where $\lambda_{k+1}$ can be zero). If no such $k$ exists, diminish the last maximal part by $1$ moving the dot by the minimal possible amount (such moves are necessary in the lower half of the chain in order to "empty" the staircase). I guess one can get a formula for the length of this chain (which can probably be shown to be of maximal length by an induction argument) in terms of triangular numbers.

The maximal length should be $2{k+1\choose 3}+\alpha k$ where $k$ is maximal such that $n={k+1\choose 2}+\alpha$ with $\alpha\in\{0,\dots,k\}$. (Without stupid mistake on my behalf.) The first values for $n=1,2,\dots$ are $$0,1,2,4,6,8,11,14,17,20,24,28,32,\dots.$$ This is sequence A6463 of the OEIS which mentions that it is the solution to the above problem!

Answer 2

This is Exercise 7.2(f) in Stanley "Enumerative Combinatorics II": The length of the longest chain in dominance order is $$\frac{1}{3}m(m^2+3r-1)$$ where $n = \binom{m+1}{2} + r$ with $0 \leq r \leq m$.