The Robinson-Schensted and Schutzenberger algorithms, an elementary approach

摘要: We discuss the Robinson-Schensted and Schutzenberger algorithms, fundamental identities they satisfy, systematically interpreting Young tableaux as chains in lattice. also derive a algorithm for hyperoctahedral groups. Finally we show how mentioned imply some properties of Schutzenberger's glissements. The two algorithms referred to our title are combinatorial dealing with tableaux. former was found originally by G. de B. Robinson (Rob), independently rediscovered much later, difierent form, C. Schensted (Sche); it establishes bijective correspondence between permutations pairs equal shape. latter (which is sometimes associated term jeu taquin) introduced M. P. (Schu1), who demonstrated its great importance relation algorithm; shape preserving involutory These have been studied mainly their own sake|they exhibit quite remarkable properties|rather than primarily serving (as usually case algorithms) means computing mathematical value. 0.1. Some history. older considered here. It flrst de- scribed 1938 paper representation theory symmetric general linear groups, particular an attempt prove correctness rule that Littlewood Richardson (LiRi) had given computation coe-cients decomposition products Schur functions. Robinson's description rather obscure however, his proof Littlewood-Richardson incomplete; apart from fact supposed reproduced (Littl), does not appear received mention literature subsequent decades. interest enjoys nowadays combinatorialists triggered independent reformulation (Sche) published 1961, whose main objective counting lengths longest increasing decreasing subsequences; recognised until several years later this essentially same Robinson's, despite deflnition. signiflcance Schensted's indi- cated at time other shall be considering (the operation called I (Schu1,x5)): he stated number important satisfled correspondences deflned relations them. That represents big step forward understanding algorithm, but results somewhat obscured complicated notation many minor errors, emphasis lies on treating limiting inflnite tableaux, generalisation has ignored further development subject.