Skip to main content
2 of 4
added 166 characters in body
Roland Bacher
  • 17.9k
  • 3
  • 45
  • 113

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.

Without mistake of my part, the maximal length is $2{k\choose 2}+\alpha k$ where $k$ is maximal such that $n={k+1\choose 2}+\alpha$ with $\alpha\in\{0,\dots,k\}$.

Roland Bacher
  • 17.9k
  • 3
  • 45
  • 113