论文标题
从Tableau Recursions获得的Robinson-Schensted算法
Robinson-Schensted Algorithms Obtained from Tableau Recursions
论文作者
论文摘要
The numbers $f_λ$ of standard tableaux of shape $λ\vdash n$ satisfy 2 fundamental recursions: $f_λ= \sum f_{λ^-}$ and $(n + 1)f_λ=\sum f_{λ^+}$, where $λ^-$ and $λ^+$ run over all shapes obtained from $λ$ by adding or removing a square respectively.这些递归中的第一个是微不足道的。第二个可以从第一个来证明代数。这些递归一起意味着代数尺寸公式$ n！ = \ sumf_λ^2 $，用于$ s_n $的不可约表示。我们表明，对这种经典代数参数的组合分析产生了无限的算法家族，其中包括经典的Robinson-Schensted行和列插入算法。我们的每种算法都会产生维度公式的射形证明。
The numbers $f_λ$ of standard tableaux of shape $λ\vdash n$ satisfy 2 fundamental recursions: $f_λ= \sum f_{λ^-}$ and $(n + 1)f_λ=\sum f_{λ^+}$, where $λ^-$ and $λ^+$ run over all shapes obtained from $λ$ by adding or removing a square respectively. The first of these recursions is trivial; the second can be proven algebraically from the first. These recursions together imply algebraically the dimension formula $n! =\sum f_λ^2$ for the irreducible representations of $S_n$. We show that a combinatorial analysis of this classical algebraic argument produces an infinite family of algorithms, among which are the classical Robinson-Schensted row and column insertion algorithms. Each of our algorithms yields a bijective proof of the dimension formula.
