Viennot

Viennot's construction, named for Xavier Gérard Viennot, is a method of finding the ordered pair \((P, Q)\) of standard tableaux that correspond to a permutation, as predicted by the Robinson-Schensted correspondence.

Given a permutation \(\sigma\) on \(n\) letters, the process begins by plotting the points \( (i, \sigma(i))\) for \(1 \leq i \leq n\). Next, imagine a light shining from the origin towards the first quadrant of a plane, resulting in each point casting a shadow towards the north east. The boundaries of these shadows reveal the first row of the tableaux. Before removing the first set of shadows, draw new points at the new vertices of the shadow lines, and repeat the process to find the successive rows of the tableaux. The process is complete when no shadow lines have any remaining vertices.

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\).

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.