Robinson–Schensted correspondence とは

数学では、Robinson-Schenstedの対応は、同じ形の標準的なヤング・テーブルーの順列と対の間の全容対応である。それはさまざまな記述を持ち、アルゴリズムの性質を持ち、多くの顕著な特性を持ち、組み合わせ理論や表現理論などの分野に応用されています。この対応は多くの方法、特にKnuthによってRobinson-Schensted-Knuthの対応として知られており、Zelevinskyによる写真へのさらなる一般化によって一般化されている。
対応の最も単純な記述は、特定の規則に従って順列の値を連続的に挿入することによって1つのテーブルを構築する手順であるSchenstedアルゴリズム(Schensted 1961)を使用することである。一方、他のテーブルは構築中に形状の進化を記録する。この対応は、リトルウッド – リチャードソンのルールを証明しようと、Robinson(Robinson 1938)によってかなり以前に書かれたものであり、かなり異なった形で記述されていた。この対応関係はRobinson-Schenstedアルゴリズムと呼ばれることが多いが、Robinsonが使用する手順はSchenstedアルゴリズムとは根本的に異なり、ほとんど完全に忘れている。対応関係を定義する他の方法には、jeu de taquinに関して非決定論的アルゴリズムが含まれます。
対応の全容的性質はそれを列挙的アイデンティティーに関連付ける:
λ P n ( t λ ) 2 = n ! {\displaystyle \sum _{\lambda \in {\mathcal {P}}_{n}}(t_{\lambda })^{2}=n!}
ここで P n {\displaystyle {\mathcal {P}}_{n}} はnの区画の集合(またはn個の正方形を有するヤング図)を示し、tλは形状λの標準的なヤングな表の数を示す。