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 can be tried using another applet).

Xavier Viennot described a means of determining the pair of tableaux associated to a permutation using ombres (shadow lines). This method is demonstrated in the applet. 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 (no larger than 20 recommended). The applet will default to the identity permutation. Change the permutation by clicking or tapping directly on the graph; this will map the associated \(x\) value to the associated \(y\) value. The applet will automatically change other values as necessary to maintain a bijective mapping.

As the permutation is updated, the associated pair of standard tableaux are displayed on the right, along with some information about the permutation. The cycles are returned in canonical form.

On a computer, hover the mouse over the boxes in each diagram to highlight the shadows associated with that row in the tableau.

This applet was created using JavaScript and the Konva graphics library.