View source for Robinson-Schensted correspondence

A [[Bijection|bijection]] between certain sequences of numbers and pairs of Young tableaux (cf. [[Young tableau|Young tableau]]), defined by means of a combinatorial algorithm. In its basic form, the Robinson–Schensted correspondence gives a bijection between the [[Symmetric group|symmetric group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r1101201.png" />, whose elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r1101202.png" /> are represented by the sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r1101203.png" />, and pairs of standard Young tableaux of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r1101204.png" /> with equal shapes. The two tableaux are usually referred to as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r1101205.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r1101206.png" />, or as the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r1101208.png" />-symbol and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012010.png" />-symbol of the permutation.

The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012011.png" />-symbol can be obtained by repeatedly applying the following so-called Schensted insertion procedure to the terms of the sequence, from left to right, to enter them into an initially empty tableau <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012012.png" />. To insert a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012013.png" />, it is placed in the first row of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012014.png" />, either by replacing the first entry greater than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012015.png" /> in that row, or if there is no such entry, by adding it to the end of the row. If a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012016.png" /> was replaced, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012017.png" /> is placed in the next row using the same rule, and so on, until at some step no number is replaced. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012018.png" />-symbol of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012019.png" /> records the successive shapes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012020.png" /> by having entry <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012021.png" /> in the square added to the shape of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012022.png" /> by insertion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012023.png" />; the final value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012024.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012025.png" />-symbol of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012026.png" />. E.g., for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012027.png" /> one has

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012028.png" /></td> </tr></table>

Given standard Young tableaux <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012030.png" /> of the same shape, this algorithm can be reversed to determine the permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012031.png" /> with these <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012032.png" />- and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012033.png" />-symbols.

The correspondence has a fundamental but non-trivial symmetry: replacing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012034.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012035.png" /> interchanges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012037.png" />. There are more symmetries, which require another algorithmically defined correspondence, namely a shape-preserving involution of the set of standard Young tableaux that is due to M.-P. Schützenberger [[#References|[a9]]]. For instance, reversing the sequence corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012038.png" /> transposes both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012039.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012040.png" />, while also applying this involution to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012041.png" />. Details can be found in [[#References|[a3]]] and [[#References|[a6]]].

A generalization of this correspondence is obtained by allowing arbitrary sequences of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012042.png" /> numbers taken from some fixed set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012043.png" />; the same algorithm then defines a bijection between the set of such sequences and pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012045.png" /> of equal shape, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012046.png" /> is still a standard Young tableau of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012047.png" />, but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012048.png" /> is now a semi-standard Young tableau (see [[Young tableau|Young tableau]]) with entries in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012049.png" />. This form gives the decomposition of the character of the representation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012050.png" /> of the [[General linear group|general linear group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012051.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012052.png" />, into irreducible characters (which are Schur polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012053.png" />, see [[Symmetric polynomial|Symmetric polynomial]]): each standard Young tableau <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012054.png" /> of shape <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012055.png" /> corresponds to a factor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012056.png" />, and each semi-standard Young tableau <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012057.png" /> of shape <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012058.png" /> and type (or weight) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012059.png" /> corresponds to a term <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012060.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012061.png" />. A further generalization, which restores the symmetry between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012062.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012063.png" />, is defined in [[#References|[a2]]], and an even further generalization, in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012064.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012065.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012066.png" /> are all [[Pictures|pictures]], is defined in [[#References|[a12]]]; it probably provides the most natural setting for the Robinson–Schensted correspondence.

Having the same <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012067.png" />-symbol defines an equivalence relation on sequences of numbers called plactic equivalence. It is generated by relations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012068.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012069.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012070.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012071.png" /> (cf. [[#References|[a2]]]); therefore, the set of equivalence classes forms a [[Monoid|monoid]] under concatenation, called the plactic monoid, which has many interesting properties, see [[#References|[a4]]].

There exist other algorithmic descriptions of the correspondence than the one given above. In fact, the description originally given by A. Robinson in an (incomplete) attempt to prove the Littlewood–Richardson rule [[#References|[a7]]] is rather different. Also, a very simple game, called the [[Jeu de taquin|jeu de taquin]], defined by Schützenberger [[#References|[a10]]] gives a non-deterministic procedure for computing the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012072.png" />-symbol. Besides providing useful enumerative identities, the correspondence itself has various useful interpretations, e.g., it defines the Kazhdan–Lusztig cells in the symmetric groups [[#References|[a1]]], and it has interpretations in terms of the geometry of the flag manifold of general linear groups [[#References|[a11]]], and of straightening [[#References|[a5]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D. Kazhdan,   G. Lusztig,   "Representations of Coxeter groups and Hecke algebras"  ''Invent. Math.'' , '''53'''  (1979)  pp. 165–184</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.E. Knuth,   "Permutations, matrices and generalized Young tableaux"  ''Pacific J. Math.'' , '''34'''  (1970)  pp. 709–727</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D.E. Knuth,   "The art of computer programming III. Sorting and searching" , Addison-Wesley  (1975)  pp. 48–72</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Lascoux,   M.P. Schützenberger,   "Le monoïde plaxique"  ''Quad. Ricerca Scient. C.N.R.'' , '''109'''  (1981)  pp. 129–156</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  B. Leclerc,   J.-Y. Thibon,   "The Robinson–Schensted correspondence, crystal bases, and the quantum straightening at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110120/r11012073.png" />"  ''Electronic J. Combinatorics'' , '''3''' :  2  (1996)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  M.A.A. van Leeuwen,   "The Robinson–Schensted correspondence and Schützenberger algorithms, an elementary approach"  ''Electronic J. Combinatorics'' , '''3''' :  2  (1996)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  G. de B. Robinson,   "On the representations of the symmetric group"  ''Amer. J. Math.'' , '''60'''  (1938)  pp. 745–760</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  C. Schensted,   "Longest increasing and decreasing subsequences"  ''Canadian J. Math.'' , '''13'''  (1961)  pp. 179–191</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  M.P. Schützenberger,   "Quelques remarques sur une construction de Schensted"  ''Math. Scand.'' , '''12'''  (1963)  pp. 117–128</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  M.P. Schützenberger,   "La correspondance de Robinson"  D. Foata (ed.) , ''Combinatoire et Représentation du Groupe Symétrique'' , ''Lecture Notes in Mathematics'' , '''579''' , Springer  (1976)  pp. 59–113</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  R. Steinberg,   "An occurrence of the Robinson–Schensted correspondence"  ''J. Algebra'' , '''113'''  (1988)  pp. 523–528</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  A.V. Zelevinsky,   "A generalisation of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence"  ''J. Algebra'' , '''69'''  (1981)  pp. 82–94</TD></TR></table>