Schensted Insertion

释义 Definition

Schensted insertion（申斯特德插入/舍恩斯特德插入）：组合数学中的一种插入算法，把一个数（或序列中的下一个元素）按规则逐步插入到杨表（Young tableau）中，通常指行插入（row insertion）过程：元素从第一行开始插入，若“顶替（bump）”了某个更大的元素，被顶替的元素再到下一行继续插入，如此递归，最终得到一个标准的（或半标准的）杨表。它是 Robinson–Schensted 对应的核心步骤之一。

发音 Pronunciation (IPA)

/ˈʃɛn.stɛd ɪnˈsɝː.ʃən/

例句 Examples

We use Schensted insertion to build a Young tableau.
我们用 Schensted 插入来构造一个杨表。

Applying Schensted insertion to the permutation yields the pair of tableaux in the Robinson–Schensted correspondence.
对这个置换应用 Schensted 插入，会得到 Robinson–Schensted 对应中的一对杨表。

词源 Etymology

该术语以数学家 Craige Schensted 命名。Schensted 在研究与最长递增子序列等问题相关的组合结构时提出了这种插入规则；后来它与 Robinson 的工作一起发展为著名的 Robinson–Schensted（RS）对应，并在表示论、对称函数与代数组合等领域广泛使用。

相关词 Related Words

• Algorithm
• Permutation
• Young Tableau
• Row Insertion
• Bumping
• Robinson–Schensted Correspondence
• Longest Increasing Subsequence
• Knuth Relations

文学与经典著作 Literary Works

• Young Tableaux: With Applications to Representation Theory and Geometry（William Fulton）
• The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions（Bruce E. Sagan）
• Enumerative Combinatorics, Volume 2（Richard P. Stanley）
• Symmetric Functions and Hall Polynomials（I. G. Macdonald）