Robinson–Schensted correspondence

Remarks

Row insertion of a number $x$ into a tableau works as follows. If $x$ is larger than every entry of the first row, put $x$ at the end of that row. Otherwise $x$ replaces the smallest entry of the row that is larger than $x$, and the replaced entry is inserted into the next row in the same way. The tableau $P(\sigma)$ is obtained by inserting $\sigma(1), \dots, \sigma(n)$ in order into the empty tableau. The tableau $Q(\sigma)$ records the step: it has entry $k$ in the cell that was created at step $k$. Each step can be undone from the position of the new cell, which gives the inverse map and proves part 1. Parts 3 and 4 are due to Schensted.

Example: for $\sigma = 2\,3\,1$ in one-line notation, inserting $2$ and $3$ gives the row $2\,3$. Inserting $1$ bumps $2$ into the second row, so $P = \begin{smallmatrix} 1 & 3 \\ 2 & \end{smallmatrix}$ and $Q = \begin{smallmatrix} 1 & 2 \\ 3 & \end{smallmatrix}$. The first row has length $2$, the length of the increasing subsequence $2\,3$.

Going deeper

For a student

Counting both sides of part 1 gives $\sum_{\lambda \vdash n} (f^\lambda)^2 = n!$, where $f^\lambda$ is the number of standard tableaux of shape $\lambda$. This matches the identity that the squares of the dimensions of the irreducible representations of $S_n$ add up to $\abs{S_n}$. By part 2, involutions correspond to single tableaux, so the number of involutions in $S_n$ is $\sum_{\lambda \vdash n} f^\lambda$. The Robinson–Schensted–Knuth correspondence extends the bijection to matrices with nonnegative integer entries and semistandard tableaux.