Robinson-Schensted algorithm

From Wikipedia, the free encyclopedia

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 Sn and pairs of standard Young tableaux of the same shape. It can be viewed as a simple, constructive proof of the combinatorial identity:

\sum_{\lambda\vdash n} (f^\lambda)^2= n!

where \lambda\vdash n means λ varies over all partitions of n and fλ is the number of standard Young tableaux of shape λ. It does this by constructing a map from pairs of λ-tableaux (P,Q) to permutations π.

Schensted, who independently discovered the algorithm, generalized it to the case where P is semi-standard and π 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.

[edit] Definition

The Robinson–Schensted algorithm starts from the permutation written in lexicographic two-line notation

\begin{matrix}1 & 2 & 3 & \cdots & n\\ \pi_1 & \pi_2 & \pi_3 & \cdots & \pi_n \end{matrix},

where π(i) = π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 = Pn and Q = Qn. The sequence is constructed by, at each step constructing Pi by inserting πi in Pi − 1 and constructing Qi by placing (adding the element at a specified corner) i into Qi − 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 Pi by row inserting πi into Pi − 1
  • Construct Qi by placing i into Qi − 1 at the same corner the insertion terminated (so that Pi and Qi have the same shape)
  • Return (Pn,Qn)

The algorithm is invertible and produces a pair of standard Young tableaux if the πi are a permutation. Moreover if the permutation π yields the pair (Pn,Qn) its inverse permuation π − 1 yields the pair (Qn,Pn).

[edit] References

  • G. de B. Robinson, "On representations of the symmetric group," Amer. J. Math. 60 (1938), 745–760. Zbl0019.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.