Clicky

Mercyhurst UniversityDept of Math and ITDr Williams Home

Robinson-Schensted Correspondence


Size of Permutation:   
  

About the 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: 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:

Using the Applet

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

As a value is chosen, it will be added to the insertion tableau, in white, 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, in grey, and is labelled in order. Each step of the insertion can be undone by clicking "Undo Last Insertion". The process is complete when all numbers have been used in the permutation. The applet will then display the permutation in cycle notation.

About this Applet

This applet was created using JavaScript and the Raphael library. If you are unable to see the applet, make sure you have JavaScript enabled in your browser. This applet may not be supported by older browsers.