Robinson-Schensted algorithm

In mathematics, the Robinson–Schensted algorithm is a combinatorial algorithm, first described by Robinson in 1938, which establishes a bijective correspondence between elements of the symmetric group $S\_n$ and pairs of standard Young tableaux of the same shape. It can be viewed as a simple, constructive proof of the combinatorial identity::$sum\_\{lambdavdash\; n\}\; (f^lambda)^2=\; n!$where $lambdavdash\; n$ means $lambda$ varies over all partitions of $n$ and $f^lambda$ is the number of standard Young tableaux of shape $lambda$. It does this by constructing a map from pairs of $lambda$-tableaux $(P,Q)$ to permutations $pi$.

Schensted, who independently discovered the algorithm, generalized it to the case where $P$ is semi-standard and $pi$ is any sequence of $n$ numbers.The Robinson–Schensted–Knuth algorithm was developed by Knuth in 1970 and establishes a bijective correspondence between generalized permutations (two-line arrays of lexicographically ordered positive integers) and pairs of semi-standard Young tableaux of the same shape.

Definition

The Robinson–Schensted algorithm starts from the permutation written in lexicographic two-line notation:,where $pi(i)=pi\_i$, and proceeds by constructing a sequence of ordered pairs of Young tableaux of the same shape::$(P\_0,Q\_0),\; (P\_1,Q\_1),(P\_2,Q\_2),ldots,(P\_n,Q\_n)$,where $P\_0=Q\_0=emptyset$ are null tableaux. The output standard tableaux are $P=P\_n$ and $Q=Q\_n$. The sequence is constructed by, at each step constructing $P\_i$ by "inserting" $pi\_i$ in $P\_\{i-1\}$ and constructing $Q\_i$ by "placing" (adding the element at a specified corner) $i$ into $Q\_\{i-1\}$.

Given a Young tableau $T$, to row insert $x$ into $T$,
* Set $R$ equal to the first row of $T$
* While $R$ contains an element greater than $x$, do:*Let $y$ be the smallest element of $R$ greater than $x$.:*Replace $y$ by $x$ in $R$.:*Set $x=y$ and set $R$ equal to the next row down.
*Place $x$ at the end of the row $R$ and stop.

Thus, the Robinson-Schensted algorithm proceeds as follows
* Set $P\_0=Q\_0=emptyset$
* For $i=1$ to $n$:*Construct $P\_i$ by row inserting $pi\_i$ into $P\_\{i-1\}$:*Construct $Q\_i$ by placing $i$ into $Q\_\{i-1\}$ at the same corner the insertion terminated (so that $P\_i$ and $Q\_i$ have the same shape)
* Return $(P\_n,Q\_n)$The algorithm is invertible and produces a pair of standard Young tableaux if the $pi\_i$ are a permutation. Moreover if the permutation $pi$ yields the pair $(P\_n,Q\_n)$ its inverse permuation $pi^\{-1\}$ yields the pair $(Q\_n,P\_n)$.

References

*G. de B. Robinson, "On representations of the symmetric group," "Amer. J. Math." 60 (1938), 745–760. Zbl [http://www.zentralblatt-math.org/zmath/en/search/?q=an:0019.25102 0019.25102]
*D. E. Knuth, "Permutations, matrices and generalized Young tableaux," "Pacific J. Math." 34 (1970), 709–727.
*B. E. Sagan, "The Symmetric Group," Graduate texts in mathematics 203 (Springer-Verlag, New York, 2001), ISBN 0387950672
*C. Schensted, "Longest increasing and decreasing subsequences," "Canad. J. Math." 13 (1961), 179–191.