Robinson-Schensted Correspondence

The Robinson-Schensted correspondence is a bijection between permutations and pairs of standard tableaux \((P,Q)\) with the same shape. The study of this correspondence has given rise to some remarkable results in combinatorics and representation theory. The correspondence was later generalized by Knuth to a bijection between matrices with nonnegative integer entries and pairs of semistandard tableaux with the same shape.

Notable properties of the correspondence include:

• If σ is a permutation that corresponds to the pair of standard tableaux \((P,Q)\), then its inverse σ\(^{-1}\) will correspond to the pair \((Q,P)\).
• As a corollary to the previous property, if σ is an involution (a permutation that is equal to its own inverse), then σ will correspond to a pair of equal tableaux \((P,P)\). Consequently, involutions on \(n\) letters are in one-to-one correspondence with standard tableaux with \(n\) boxes.
• If σ is an involution, the number of odd columns of the corresponding tableaux will be equal to the number of points fixed by σ.
• With a permutation σ written in one line notation, the lengths of the longest increasing and decreasing subsequences of σ will corresponding to the lengths of the first row and column, respectively, of the corresponding tableaux.

Gilbert de Beauregard Robinson first described the bijection between permutations and pairs of standard tableaux with the same shape in 1938, while studying the Littlewood-Richardson Rule. Though he provided a means of finding the corresponding tableaux when given a permutation, another algorithm described by Craige Eugene Schensted in 1961 is more widely used today. The bijection between matrices with non-negative integer entries and pairs of semi standard tableaux with the same shape was described by Donald E. Knuth in 1970.

Other constructions for these bijections exist. Xavier Viennot described a means of determining the pair of tableaux associated to a permutation using ombres (shadow lines). William Fulton, in his book Young Tableaux, explains the matrix ball algorithm for finding the pair of semi standard tableaux associated to a matrix with nonnegative integer entries.

More information about the RSK algorithm can be found in the following sources:

• William Fulton. Young Tableaux, volume 35 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1997.
• Bruce E. Sagan. The Symmetric Group, volume 203 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2001.
• Richard P. Stanley. Enumerative Combinatorics. Cambridge University Press, Cambridge, 1999.