Schensted insertion algorithm

Suppose we have the permutation $w = w_{1}, \dots, w_{n}$ . This algorithm constructs a pair of Young tableau(x)s with the same shape associated to it.

The shape of the resulting tableaux is called the Schensted shape of a permutation.

Properties

If we construct $w \to (P, Q)$ , then the inverse permutation $w^{- 1} \to (Q, P)$

Algorithm

To construct $P$ , the insertion tableau:

For each $i \in [w_{1}, \dots, w_{n}]$
- If $i$ is larger than all the entries in the first row, add a new box at the end of the row and label it $i$
- Otherwise, replace the smallest entry larger than $i$ (let's call it $i^{'}$ ) with $i$ .
- Repeat this process with $i^{'}$ for the next row

To construct $Q$ , the recording tableaux:

It has the same shape as $P$ and you label each box with the order in which that box was created when you were performing the algorithm on $P$ .

Now we need to give an inverse with this algorithm:

Find the max entry in $Q$
Find the corresponding entry in $P$ , say $i$
Iterate until you reach the first row:
1. Look for the max entry in the previous row (above) that is less than $i$
2. Set this to be the new $i$
When you reach the first row, the number that you pick is the last element of the permutation.