Robinson–Schensted correspondence

In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics and other areas such as representation theory. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence, and a further generalization to pictures by Zelevinsky.

The simplest description of the correspondence is using the Schensted algorithm (Schensted 1961), a procedure that constructs one tableau by successively inserting the values of the permutation according to a specific rule, while the other tableau records the evolution of the shape during construction. The correspondence had been described, in a rather different form, much earlier by Robinson (Robinson 1938), in an attempt to prove the Littlewood–Richardson rule. The correspondence is often referred to as the Robinson–Schensted algorithm, although the procedure used by Robinson is radically different from the Schensted algorithm, and almost entirely forgotten. Other methods of defining the correspondence include a nondeterministic algorithm in terms of jeu de taquin.

The bijective nature of the correspondence relates it to the enumerative identity

∑

λ

∈

P

n

(

t

λ

)

2

=

n

!

{\displaystyle \sum _{\lambda \in {\mathcal {P}}_{n}}(t_{\lambda })^{2}=n!}

where

P

n

{\displaystyle {\mathcal {P}}_{n}}

denotes the set of partitions of n (or of Young diagrams with n squares), and tλ denotes the number of standard Young tableaux of shape λ.

The Schensted algorithm

The Schensted algorithm starts from the permutation σ written in two-line notation

σ

=

(

1

2

3

⋯

n

σ

1

σ

2

σ

3

⋯

σ

n

)

{\displaystyle \sigma ={\begin{pmatrix}1&2&3&\cdots &n\\\sigma _{1}&\sigma _{2}&\sigma _{3}&\cdots &\sigma _{n}\end{pmatrix}}}

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

(

P

0

,

Q

0

)

,

(

P

1

,

Q

1

)

,

…

,

(

P

n

,

Q

n

)

,

{\displaystyle (P_{0},Q_{0}),(P_{1},Q_{1}),\ldots ,(P_{n},Q_{n}),}

where P0 = Q0 are empty tableaux.