Take the 2-minute tour ×

It is well known that the number of rows in the semistandard Young tableaux correspondent to a two-line array via RSK is equal to the length of the longest (strictly) decreasing subsequence in the array's second line, in the case the array's columns are ordered lexicographically. Note that this statement by itself involves nothing more than the definition of Schensted's row insertion procedure (row bumping). Namely, it can be rephrased in the following way: the number of rows in $(\ldots((\emptyset\leftarrow x_1)\leftarrow x_2)\leftarrow\ldots)\leftarrow x_n$ is equal to the length of the longest decreasing subsequence in $(x_1,x_2,\ldots,x_n)$, where $\leftarrow$ is row insertion and $\emptyset$ denotes the empty tableau.

However, proofs of this fact I've come across are quite complicated in the sense that they tend to employ some more or less advanced theoretic basis. For an example see exercise 1 in §3.2 of W. Fulton's book "Young tableaux: with applications to representation theory and geometry" and the proposed solution to it. I'm looking for a short self-contained proof of the above statement considering row insertion.

Actually, I'd be more than satisfied by such a proof for the number of rows not exceeding the length of the longest decreasing subsequence. Note that the in a way dual fact of the number of columns not exceeding the length of the longest nondecreasing subsequence is nearly obvious. It may not be obvious but can certainly be proven very simply, see Schensted's original paper.

Clarification. By short I mean really short. Short enough to post as 1-2 screen long answer here without a single external reference. Once again, the motivation here is that the standard proof of the "dual" statement definitely satisfies this criterion.

share|improve this question
I don't have Fulton's book at hand, so can you clarify: you are not happy with proving the statement about the number of columns and applying the involution? I think this is more or less how the original Schensted proof can be rephrased. –  Vladimir Dotsenko Mar 8 '12 at 8:36
Well... Yes, to keep it simple let's say I'm just looking for a considerably shorter proof than the one in Schensted's paper. –  Igor Makhlin Mar 8 '12 at 11:27
I had a feeling that, since the statement about the number of columns can be proven so easily, the same must hold for the number of rows, in fact I was hoping for a similar argument. Also I'm not quite sure what the involution statement is for SSYTs but that's probably due to my own ignorance. –  Igor Makhlin Mar 8 '12 at 11:50
I am sorry for being unclear - apparently, two statements got confused in my head. Alas, the "involution" argument I thought of is in fact trickier than I hoped, the correct statement is in this answer of Richard Stanley: mathoverflow.net/questions/14527/… - but if you look the original paper of Knuth (projecteuclid.org/euclid.pjm/1102971948) you'll see there a somewhat down-to-earth (though not short) argument why the first tableau for $(x_n,\ldots,x_1)$ is the first tableau $(x_1,\ldots,x_n)$ transposed. –  Vladimir Dotsenko Mar 8 '12 at 12:52
Is Viennot's proof too long? (you can find an exposition in Bruce Sagan's Book) –  Martin Rubey Mar 8 '12 at 13:03

Your Answer



Browse other questions tagged or ask your own question.