# Number of Longest Decreasing subsequences and RSK

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)

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)

• You probably know this, but I figure it's worth reminding people that π is an involution if and only if P and Q (the tableaux under RSK) are equal. – Jonah Ostroff Nov 10 '10 at 14:13
• Agreed. I edited accordingly. – Vasu vineet Nov 11 '10 at 2:32
• @Vasu-vineet, while you do have a link to a page explaining the Robinson-Schensten-(Knuth) RSK correspondence, you never specifically state the full name of the algorithm. Others reading this page would be a bit mystified and may not bother clicking through to read the details of concept which establishes a bijective correspondence between elements of the symmetric group $S_n$ and pairs of standard Young tableaux of the same shape. Also, your wikipedia link has malformed characters in it and doesn't work. Try en.wikipedia.org/wiki/Robinson-Schensted_algorithm – sleepless in beantown Nov 11 '10 at 2:56