Robinson–Schensted correspondence

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, the Robinson–Schensted correspondence is a <a href="/facts/Bijection/j4gTuTmW">bijective</a> correspondence between <a href="/facts/Permutation/JSw9ukmv">permutations</a> and pairs of standard <a href="/facts/Young_tableaux/e5lI4bck">Young tableaux</a> 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 <a href="/facts/Combinatorics/k14xUoKT">combinatorics</a> and other areas such as <a href="/facts/Representation_theory/3ydLtaGH">representation theory</a>. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the <a href="/facts/Robinson%25E2%2580%2593Schensted%25E2%2580%2593Knuth_correspondence/jUoUr62v">Robinson–Schensted–Knuth correspondence</a>, and a further generalization to <a href="/facts/Picture_(mathematics)/YRMHLypg">pictures</a> by <a href="/facts/Andrei_Zelevinsky/sQBoglf4">Zelevinsky</a>.
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 (<a href="/facts/Gilbert_de_Beauregard_Robinson/fjQrU8qJ">Robinson</a> 1938), in an attempt to prove the <a href="/facts/Littlewood%25E2%2580%2593Richardson_rule/8NSx5K36">Littlewood–Richardson rule</a>. 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 <a href="/facts/Nondeterministic_algorithm/UubLdp3D">nondeterministic algorithm</a> in terms of <a href="/facts/Jeu_de_taquin/5NNAkICX">jeu de taquin</a>.
The bijective nature of the correspondence relates it to the <a href="/facts/Enumerative_combinatorics/AtqWU2bj">enumerative</a> 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 <a href="/facts/Partition_(number_theory)/LtyXWqwH">partitions</a> of n (or of <a href="/facts/Young_diagram/e5lI4bck">Young diagrams</a> with n squares), and tλ denotes the number of standard Young tableaux of shape λ.

Robinson–Schensted correspondence open-in-new

Robinson–Schensted correspondence