Robinson-Schensted Correspondence

The Robinson-Schensted correspondence is a bijection between permutations and pairs of standard Young tableaux of the same shape: given a permutation, it produces two tableaux with identical shape and the same number of entries. It is most often computed by the Schensted algorithm, a step-by-step insertion procedure devised by Craige Schensted in 1961 that builds one tableau by inserting the permutation's values in turn according to fixed rules, while a second tableau records how the shape grows at each step. The underlying correspondence was actually first described in 1938 by Gilbert de Beauregard Robinson, in a substantially different and now largely forgotten form, developed while he was working toward a proof of the Littlewood-Richardson rule; Schensted's later algorithmic reformulation became the standard way the correspondence is presented and computed. Because it relates the number of permutations to properties of standard Young tableaux, the correspondence is a foundational tool in combinatorics and representation theory. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/