= Solution
For <permutations>, the <Robinson-Schensted-Knuth correspondence>, also called the <permutation> case of <RSK>, is a <bijection>
$$
\boxed{S_n\longleftrightarrow\{(P,Q):P,Q\text{ standard tableaux of the same shape }\lambda\vdash n\}.}
$$
Process the word $\sigma(1),\ldots,\sigma(n)$ by <row insertion> to form $P$. To insert a new entry $a$, replace the leftmost entry of the first row larger than $a$ and bump that displaced entry into the next row by the same rule. If a row has no larger entry, append $a$ at its end and stop. Exactly one outer-corner cell is added. Record the current insertion time in that new cell of $Q$.
Rows stay increasing by the choice of the leftmost larger entry. The inequalities between successive bumped entries and the entries above them preserve increasing columns. Successive shapes are <Young diagrams>, so the recording labels also increase across rows and down columns. Reverse insertion at the corner labelled $n$ in $Q$ recovers the last input entry; repeating it recovers the full <permutation>, proving bijectivity. The more general <RSK correspondence> extends this construction to suitable two-line arrays and <semistandard tableaux>.
Back to article page
