Robinson–Schensted correspondence

In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. 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 correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence, and a further generalization to pictures by Zelevinsky. In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. 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 correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence, and a further generalization to pictures by Zelevinsky. 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. The correspondence had been described, in a rather different form, much earlier by Robinson (Robinson 1938), in an attempt to prove the Littlewood–Richardson rule. The correspondence is often referred to as the Robinson–Schensted algorithm, although the procedure used by Robinson is radically different from the Schensted–algorithm, and almost entirely forgotten. Other methods of defining the correspondence include a nondeterministic algorithm in terms of jeu de taquin. The bijective nature of the correspondence relates it to the enumerative identity: where P n {displaystyle {mathcal {P}}_{n}} denotes the set of partitions of n (or of Young diagrams with n squares), and tλ denotes the number of standard Young tableaux of shape λ. 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. The output tableaux are P = Pn and Q = Qn. Once Pi−1 is constructed, one forms Pi by inserting σi into Pi−1, and then Qi by adding an entry i to Qi−1 in the square added to the shape by the insertion (so that Pi and Qi have equal shapes for all i). Because of the more passive role of the tableaux Qi, the final one Qn, which is part of the output and from which the previous Qi are easily read off, is called the recording tableau; by contrast the tableaux Pi are called insertion tableaux. The basic procedure used to insert each σi is called Schensted insertion or row-insertion (to distinguish it from a variant procedure called column-insertion). Its simplest form is defined in terms of 'incomplete standard tableaux': like standard tableaux they have distinct entries, forming increasing rows and columns, but some values (still to be inserted) may be absent as entries. The procedure takes as arguments such a tableau T and a value x not present as entry of T; it produces as output a new tableau denoted T ← x and a square s by which its shape has grown. The value x appears in the first row of T ← x, either having been added at the end (if no entries larger than x were present), or otherwise replacing the first entry y > x in the first row of T. In the former case s is the square where x is added, and the insertion is completed; in the latter case the replaced entry y is similarly inserted into the second row of T, and so on, until at some step the first case applies (which certainly happens if an empty row of T is reached). More formally, the following pseudocode describes the row-insertion of a new value x into T.