Viennot's Ombre Construction
Size of Permutation:  
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.

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 (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:
Using the applet
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. The first number chosen is σ(1), the second is σ(2), etc.

As the permutation grows, corresponding points are plotted in the graph window. Once the permutation is complete, you'll construct the tableaux simultaneously, one row at a time. The initial \(x\) value of each shadow line adds a new entry to the \(Q\) tableau, and the final \(y\) value of each shadow line adds a new entry to the \(P\) tableau.
About the applet
This applet was created using JavaScript and the P5 graphics library. It was last updated in February 2022.