Number of longest decreasing subsequences and RSK

Question

It is well known via the RSK-correspondence that the length of the longest decreasing subsequence in a permutation $\pi \in S_n$ is the length of the longest column of the insertion tableau of $\pi$. (The insertion tableau and the recording tableau produced by this algorithm have the same shape.)

Robinson–Schensted correspondence - Wikipedia

My question is what else can be gleaned from the RSK correspondence in terms of, say,

a) the length of the next longest decreasing subsequence in $\pi$?

b) the number of longest decreasing subsequences in $\pi$, given the fact that there is exactly one column of maximum length?

c) can we say more about the above two questions if we knew that $\pi$ was an involution? (If $\pi$ happens to be an involution, then insertion tableau and recording tableau produced are equal.)

Answer 1

For a version of a), see C. Greene, An extension of Schensted's theorem, Advances in Mathematics, 1974. Note: the result is beautiful, but the statement is a bit delicate.

Answer 2

To complete Igor's answer (whose C. Greene's quotation is perfect), for a permutation $\pi \in S_n$ with $T$ its insertion tableau. Let $$ \lambda_1\geq \cdots \geq \lambda_q $$ be the shape of $T$ (sequence of row lengths). Then

$\lambda_1$ the length of the longest increasing subsequence

$\lambda_1+\lambda_2$ is the length of the longest subsequence which is the shuffle of two increasing subsequences

...

$\lambda_1+\cdots \lambda_k$ is the length of the longest subsequence which is the shuffle of $k$ increasing subsequences.

Marcel-Paul Schützenberger used to call these numbers (during my Ph. D. supervision) "Greene Invariants".

For example for the permutation $13582467$ with insertion tableau
$$ T = \begin{bmatrix} 1 & 3 & 5 & 8\cr 2 & 4 \cr 6 \cr 7\cr \end{bmatrix} $$ of shape $(\lambda_1,\lambda_2,\lambda_3,\lambda_4)=(4,2,1,1)$, the Greene invariants are $(4,6,7,8)$. Reversing the orders (reading the permutation from right to left or reversing numbers $k\mapsto n+1-k$) you can get dual statements.