Knuth Equivalence

释义 Definition

Knuth 等价（Knuth equivalence）：组合数学中定义在排列（permutations）上的一种等价关系。两个排列若能通过一系列 Knuth 关系（Knuth relations）相互变换（在不改变某些相对次序信息的情况下交换相邻元素），则称它们 Knuth 等价。等价类与 Robinson–Schensted（RS）插入密切相关：Knuth 等价的排列会得到相同的插入杨表（insertion tableau）。

发音 Pronunciation (IPA)

/kəˈnuːθ ɪˈkwɪvələns/

词源 Etymology

“Knuth”来自美国计算机科学家 Donald E. Knuth（唐纳德·克努斯）的姓氏；“equivalence”意为“等价性/等价关系”。该术语用于描述由 Knuth 提出的局部变换规则所生成的等价关系，后来成为研究 杨表、对称函数、plactic monoid（柏拉克单子）等主题的核心概念之一。

例句 Examples

Two permutations are Knuth equivalent if they yield the same insertion tableau.
如果两个排列得到相同的插入杨表，那么它们是 Knuth 等价的。

Under the Robinson–Schensted correspondence, Knuth equivalence classes can be studied via the structure of Young tableaux and their shapes.
在 Robinson–Schensted 对应下，可以通过杨表及其形状的结构来研究 Knuth 等价类。

相关词 Related Words

• Combinatorics
• Equivalence Relation
• Knuth Relation
• Permutation
• Plactic Monoid
• Robinson–Schensted
• Young Tableau
• Insertion Algorithm

文学与著作 Literary Works

• Donald E. Knuth，《The Art of Computer Programming》（《计算机程序设计艺术》）中讨论与 RS 对应、杨表与相关变换思想相连的内容背景（Knuth 关系/等价在相关章节与文献体系中常被引用）。
• Richard P. Stanley，《Enumerative Combinatorics》（《枚举组合数学》）中在杨表、RS 对应与相关等价类的语境下提及并使用 Knuth 等价。
• Lothaire，《Algebraic Combinatorics on Words》中在 plactic monoid 等主题下使用 Knuth 等价/Knuth 关系来刻画词与排列的等价类结构。