Robinson-Schensted algorithm

From Wikipedia, the free encyclopedia

In mathematics, the Robinson–Schensted algorithm is a combinatorial algorithm, first discovered 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:

where 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. 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.

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

,

where π(i) = π_i, and proceeds by constructing a sequence of ordered pairs of Young tableaux of the same shape:

,

where 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 π_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
• For i = 1 to n

• Construct P_i by row inserting 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.

[edit] References

• G. de B. Robinson, "On representations of the symmetric group," Amer. J. Math. 60 (1938), 745–760.
• 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).
• C. Schensted, "Longest increasing and decreasing subsequences," Canad. J. Math. 13 (1961), 179–191.