在数学中,杨表 (英語:Young tableau ),又称杨氏矩阵 ,是组合表示理论和舒伯特演算 領域的常用工具。在對稱群 和一般线性群 性質的研究中,楊表提供了一個方便的方式来描述的它們的群表示 。杨表由剑桥大学 数学家 阿爾弗雷德·楊 在 1900 年提出[ 1] [ 2] 。接著於 1903 年被弗罗贝尼乌斯 应用于对称群的研究中。他们的理论由许多数学家进一步发展,包括珀西·麥克馬洪 、威廉·瓦伦斯·道格拉斯·霍奇 、G. de B. Robinson、吉安-卡洛·羅塔 、Alain Lascoux、Marcel-Paul Schützenberger 和理查德·P·史丹利 等。
定义
注意:本條目使用英式畫法來展示楊圖及楊表。
楊图
整數分拆 (5,4,1) 對應的楊圖,英式畫法
楊圖由有限多個相鄰的方格排列而成,其中,各橫行的左邊對齊,長度由下而上遞增。有時會用其他的符號代替方塊,特別的。當使用圓點代替,該圖被稱作費瑞爾圖 。若將楊圖的各行的方格數列出,則形成總方格數 n 的一個整數分拆 λ。因此,此圖可以被視為是 λ 的形狀,因為它和 λ 攜帶了相同的資訊。楊圖之間的包含關係定義出整數分拆 上的一個偏序关系 ,此關係擁有格 的結構,稱作楊氏方格 。若將楊圖的各列的方格數列出,會形成整數分拆 λ 的「共軛分拆」,或稱「轉置分拆」,它所對應到的楊圖可由原本的楊圖沿主對角線作鏡射對稱而得。
給定一個楊圖,各方格的位置由兩個座標決定,分別是行數與列數,列的順序是由左往右數,行的順序則是按照所包含的方格數由多的往少的方向數,此處牽涉到楊圖的兩種常見畫法。第一種畫法常用於法語世界 ,將各行由大到小一層一層往上疊,稱為法式畫法 ,第二種畫法常用於英语世界 ,將方格數較少的行排在方格數較多的行的下方,稱為英式畫法 。例如,在伊恩·G·麥唐諾 著作《對稱函數與赫爾多項式》[ 3] 建議習慣法式畫法的讀者將書放在鏡子中上下顛倒來看。英式畫法的思維與矩陣雷同,而法式畫法則比較接近笛卡尔坐标系 ,不過,法式畫法中對於方格的位置習慣先寫縱坐標。例如,右圖表示的,是 10 的整數分拆 (5, 4, 1) 對應的楊圖,而它的共軛分拆 (3, 2, 2, 2, 1) 則代表著各列的方格數。
勾長、臂長和腿长
在許多理論及應用中,勾長扮演非常重要的角色。給定一個整數分拆 λ,以及 λ 中的一個方格 □,其「臂長」 aλ (□) 定義成 □ 正右方的方格數,「腿長」 lλ (□) 正下方的方格數 (腿長的名稱來源自英式畫法) ,「勾長」 hλ (□) 定義為 aλ (s)+lλ (s)+1。
楊表
整數分拆 (5,4,1) 對應到的一个标准楊表
一個楊表是將楊圖中的各個方格填入一些元素,一般會填入全序集合 的元素。原本,填入的元素應該要寫作 x1 , x2 , x3 ...,但為了方便起見,都直接填入正整數。楊表最初應用於對稱群 的表示理論 時,允許在楊圖的 n 的方格中任意填入 1 到 n 中相異的正整數。不過現在的研究大多集中在「標準」的楊表,也就是上述的條件再加上各行與各列中的方格中的數字皆為嚴格遞增的。由 n 個方格的相異楊表數個數形成對和數
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (OEIS 數列A000085 )。
在其他的應用中,楊圖被允許填入相同的數字。若其填法滿足同一列中的數字嚴格遞增,且同一行中的數字單調遞增,則該楊表被稱為是「半標準的」,或有時特別稱為列嚴格的以避免定義上的歧異。將楊表中個數字出現的次數記錄下來,可得一序列,該序列被視為楊表的「權重」。因此,標準楊表的權重必然是 (1,1,...,1),因為在標準楊表中,1 到 n 的正整數恰好各出現一次。
變體
半標準楊表有許多變體,例如行嚴格楊表要求同一行中的數字嚴格遞增,且同一列中的數字單調遞增,也就是列嚴格楊表的共軛。此外,在平面分拆 的理論中,往往習慣考慮將上述的定義中的遞增改為遞減。其他變體例如帶狀楊表,其定義為在先將一些方塊打包成群,然後要求各群的方塊必須填入相同數字。
斜楊表
整數分拆 (5,4,1) 對應到的一个标准斜楊表
給定兩個楊圖 λ=(λ1 , λ2 ...)、μ=(μ1 , μ2 ...),滿足 λ 包含 μ,即 μi ≤λi 對所有 i。定義「斜楊圖」 λ/μ 為 λ 中的所有方格扣掉 μ 中的所有方格,也就是 λ 差集 μ,在斜楊圖的各方格中填入元素則形成「斜楊表」。同理,若滿足同一列中的數字嚴格遞增,且同一行中的數字單調遞增,則該斜楊表被稱作半標準的;若半標準的斜楊表滿足各方格不重複的填入數字 1 到 n,其中 n 是斜楊表所含的方格數,則該斜楊表被稱作標準的。注意到不同的 λ 和 μ 可以給出相同的 λ/μ,而且大部分斜楊表的性質都只依賴於差集完的方格,但是仍然有作用在斜楊表運算 依賴於 λ 和 μ 的選取。因此,λ/μ 必須被視為包含兩個資訊:λ 和 μ,縱使兩個斜楊表有相同形狀的方格排列,方格中填入的元素也相同,他們仍然可能是不同的。當 μ 是空分拆 (0 的唯一一種分拆) 時,斜楊表 λ/μ 就變成楊表 λ。
一個標準的斜楊表 λ/μ 可以被視為一個整數分拆的序列,起始於 μ,每次增加一個方格,最後一個是 λ,更精確一點來說,該序列第 i 個分拆是 μ 聯集所有的方格滿足它裡面的數字 ≤i。若 λ/μ 只是半標準的,仍可被視為是一個整數分拆的序列,但每次增加的方格數可能多於一個,根據半標準楊表的定義,在同一列中每次至多增加一個方格,而這個形狀被稱作「水平條」。該序列完全決定了 λ/μ 與各方格填入的數字,所以也有作者以此來當作(半)標準楊表的定義,例如伊恩·G·麥唐諾 [ 3] 。此定義包含了 λ、μ 和所有方格中的資訊。
楊表應用的概述
楊表經常應用於在组合学 、表示理論 和代數幾何 中,各種不同的計算楊表個數的方法給出舒爾函數 的定義以及相關的恆等式。此外,許多關於楊表的組合演算法已經被發現了,例如 Schützenberger 提出的 jeu de taquin 以及 RSK 對應 。Lascoux 和 Schützenberger 研究一個定義在半標準楊表上面的乘積,該乘積滿足結合律 ,並且給出一個稱為 le monoïde plaxique (法語) 的結構。
在表示理论的应用
一个杨表的表示
给定一个杨表π λ ,一共有n个方格。那么把1到n这n个数字填到这个杨表中,使得每行从左到右都是递增的,每列从下到上也是递增的。用 dimπ λ 表示这样的方法个数,如图,这个这种填写数字中的一种。我们有下面的勾长公式。
勾长
一个杨表的勾长
对于杨表中的一个方格v,其勾长 hook(v)等于同行右边的方格数加上同列上面的方格数,再加上1(也就是他自己)。
勾长公式
用 dimλ 表示这样的方法个数,勾长公式就是方法个数等于n!除以所有方格的勾长的乘积。
dim
-->
π π -->
λ λ -->
=
n
!
∏ ∏ -->
x
∈ ∈ -->
Y
(
λ λ -->
)
h
o
o
k
(
x
)
.
{\displaystyle \dim \pi _{\lambda }={\frac {n!}{\prod _{x\in Y(\lambda )}\mathrm {hook} (x)}}.}
对于分拆10 = 5 + 4 + 1 的应的杨表. 因此有
dim
-->
π π -->
λ λ -->
=
10
!
7
⋅ ⋅ -->
5
⋅ ⋅ -->
4
⋅ ⋅ -->
3
⋅ ⋅ -->
1
⋅ ⋅ -->
5
⋅ ⋅ -->
3
⋅ ⋅ -->
2
⋅ ⋅ -->
1
⋅ ⋅ -->
1
=
288.
{\displaystyle \dim \pi _{\lambda }={\frac {10!}{7\cdot 5\cdot 4\cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot 1}}=288.}
种方法。
參考資料
^ Knuth, Donald E. , The Art of Computer Programming , Vol. III: Sorting and Searching 2nd, Addison-Wesley: 48, 1973, Such arrangements were introduced by Alfred Young in 1900 .
^ Young, A., On quantitative substitutional analysis, Proceedings of the London Mathematical Society, Ser. 1, 1900, 33 (1): 97–145, doi:10.1112/plms/s1-33.1.97 . See in particular p. 133.
^ 3.0 3.1 Macdonald, Ian . Symmetric Functions and Hall Polynomials (PDF) . Oxford University Press. 12月22日: 2, 4 [2019-01-27 ] . ISBN 978-0198739128 . (原始内容 (PDF) 存档于2019-01-28).