321-avoiding permutations and RSK I am reading through a book on enumeration and I came across a weird statement:
Using RSK (Robinson-Schensted-Knuth Correspondence), one can show that 321-avoiding permutations are Catalan objects.
So... I know how to relate some paths in permutation matrices representing 321-avoiding permutations to the Catalan numbers, but I have no idea how RSK can fit into any of this.  Is there a more elegant proof using tableaux and RSK that is standard somewhere?
 A: I can't tell if it's more elegant or direct than what you already know, but the following is an argument that I found in Richard Stanley's recent book Catalan Numbers (more precisely, in problems 115, 168 and 169):
Applying RSK to a 321-avoiding permutation $\sigma \in S_n$, you get a pair of SYTs $(P,Q)$ of the same shape, each with $n$ boxes and at most two rows, since the number of rows is the length of the longest decreasing subsequence of $\sigma$.
Then you replace each number $k$ in $Q$ by $2n+1-k$, rotate the whole tableau by 180 degrees, and attach it to $P$ by juxtaposition, in such a way that you get an SYT $R$ of shape $(n,n)$ (i.e., two rows with $n$ boxes in each, and the numbers $1,2,\dots,2n$ filled in).
Next, from $R$ you get a Dyck path with $2n$ steps, from $(0,0)$ to $(2n,0)$ and never below the $y$ axis, by letting the $k$th step (for $1 \le k \le 2n$) be north-east if $k$ is in the first row of $R$, and south-east if $k$ is in the second row of $R$.
Such Dyck paths are the archetypical Catalan objects, and all the maps above are bijections, which shows that 321-avoiding permutations are Catalan objects too.
