MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

link text

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)

share|cite|improve this question
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 – sleepless in beantown Nov 11 '10 at 2:56

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.

share|cite|improve this answer
This looks interesting. I'll take a look at what this offers. Thanks. – Vasu vineet Nov 11 '10 at 2:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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