Robinson–Schensted correspondence

It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics and other areas such as representation theory.

The simplest description of the correspondence is using the Schensted algorithm (Schensted 1961), a procedure that constructs one tableau by successively inserting the values of the permutation according to a specific rule, while the other tableau records the evolution of the shape during construction.

Other methods of defining the correspondence include a nondeterministic algorithm in terms of jeu de taquin.

The Schensted algorithm starts from the permutation σ written in two-line notation where σi = σ(i), and proceeds by constructing sequentially a sequence of (intermediate) ordered pairs of Young tableaux of the same shape: where P0 = Q0 are empty tableaux.

On the other hand the new value is not less than its left neighbour (if present) either, as is ensured by the comparison that just made step 2 terminate.

It can be seen that given any pair (P, Q) of standard Young tableaux of the same shape, there is an inverse procedure that produces a permutation that will give rise to (P, Q) by the Schensted algorithm.