Robinson-Schensted Algorithm

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.

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.
The descent set of a sequence is a list of indices of terms in the sequence that are larger than the next consecutive term. The descent set of a permutation (in one-line notation) is equal to the set of values \(i\) in the \(Q\) tableaux for which \(i+1\) appears in a row below that containing \(i\).

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 and is what this applet is based on.

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.

A 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.

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.

Begin by choosing the size of the permutation you would like to enter. The applet supports permutations on up to 15 letters. Enter a permutation σ by clicking the blue buttons. You can use a keyboard to enter single digit values. The first number chosen is σ(1), the second is σ(2), etc.

As a value is chosen, it will be added to the insertion tableau on the left, \(P\), according to the Schensted algorithm. When the slide is complete and a new box is added to the shape of the insertion tableau, a box in the same location is added to the recording tableau on the right, \(Q\), and is labelled in order. The process is complete when all numbers have been used in the permutation. The applet will then display the permutation in cycle notation.