跳至內容

楊表

維基百科,自由的百科全書

在數學中,楊表(英語:Young tableau),又稱楊氏矩陣,是組合表示理論和舒伯特演算領域的常用工具。在對稱群一般線性群性質的研究中,楊表提供了一個方便的方式來描述的它們的群表示。楊表由劍橋大學數學家阿爾弗雷德·楊英語Alfred Young 在 1900 年提出[1][2]。接着於 1903 年被弗羅貝尼烏斯應用於對稱群的研究中。他們的理論由許多數學家進一步發展,包括珀西·麥克馬洪英語Percy MacMahon威廉·瓦倫斯·道格拉斯·霍奇、G. de B. Robinson、吉安-卡洛·羅塔、Alain Lascoux、Marcel-Paul Schützenberger 和理查德·P·史丹利英語Richard P. Stanley 等。

定義

注意:本條目使用英式畫法來展示楊圖及楊表。

楊圖

整數分拆 (5,4,1) 對應的楊圖,英式畫法

楊圖由有限多個相鄰的方格排列而成,其中,各橫列的左邊對齊,長度由下而上遞增。有時會用其他的符號代替方塊,特別的。當使用圓點代替,該圖被稱作費瑞爾圖。若將楊圖的各列的方格數列出,則形成總方格數 n 的一個整數分拆 λ。因此,此圖可以被視為是 λ 的形狀,因為它和 λ 攜帶了相同的資訊。楊圖之間的包含關係定義出整數分拆上的一個偏序關係,此關係擁有的結構,稱作楊氏方格。若將楊圖的各行的方格數列出,會形成整數分拆 λ 的「共軛分拆」,或稱「轉置分拆」,它所對應到的楊圖可由原本的楊圖沿主對角線作鏡射對稱而得。

給定一個楊圖,各方格的位置由兩個座標決定,分別是行數與列數,行的順序是由左往右數,列的順序則是按照所包含的方格數由多的往少的方向數,此處牽涉到楊圖的兩種常見畫法。第一種畫法常用於法語世界,將各列由大到小一層一層往上疊,稱為法式畫法,第二種畫法常用於英語世界,將方格數較少的列排在方格數較多的列的下方,稱為英式畫法。例如,在伊恩·G·麥唐諾英語Ian G. Macdonald著作《對稱函數與赫爾多項式》[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 個方格的相異楊表數個數形成對和數英語Involution number

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (OEIS數列A000085)。

在其他的應用中,楊圖被允許填入相同的數字。若其填法滿足同一行中的數字嚴格遞增,且同一列中的數字單調遞增,則該楊表被稱為是「半標準的」,或有時特別稱為行嚴格的以避免定義上的歧異。將楊表中個數字出現的次數記錄下來,可得一序列,該序列被視為楊表的「權重」。因此,標準楊表的權重必然是 (1,1,...,1),因為在標準楊表中,1 到 n 的正整數恰好各出現一次。

變體

半標準楊表有許多變體,例如列嚴格楊表要求同一列中的數字嚴格遞增,且同一行中的數字單調遞增,也就是行嚴格楊表的共軛。此外,在平面分拆英語plane partition的理論中,往往習慣考慮將上述的定義中的遞增改為遞減。其他變體例如帶狀楊表,其定義為在先將一些方塊打包成群,然後要求各群的方塊必須填入相同數字。

斜楊表

整數分拆 (5,4,1) 對應到的一個標準斜楊表

給定兩個楊圖 λ=(λ1, λ2 ...)、μ=(μ1, μ2 ...),滿足 λ 包含 μ,即 μi≤λi 對所有 i。定義「斜楊圖」 λ/μ 為 λ 中的所有方格扣掉 μ 中的所有方格,也就是 λ 差集 μ,在斜楊圖的各方格中填入元素則形成「斜楊表」。同理,若滿足同一行中的數字嚴格遞增,且同一列中的數字單調遞增,則該斜楊表被稱作半標準的;若半標準的斜楊表滿足各方格不重複的填入數字 1 到 n,其中 n 是斜楊表所含的方格數,則該斜楊表被稱作標準的。注意到不同的 λ 和 μ 可以給出相同的 λ/μ,而且大部分斜楊表的性質都只依賴於差集完的方格,但是仍然有作用在斜楊表運算依賴於 λ 和 μ 的選取。因此,λ/μ 必須被視為包含兩個資訊:λ 和 μ,縱使兩個斜楊表有相同形狀的方格排列,方格中填入的元素也相同,他們仍然可能是不同的。當 μ 是空分拆 (0 的唯一一種分拆) 時,斜楊表 λ/μ 就變成楊表 λ。

一個標準的斜楊表 λ/μ 可以被視為一個整數分拆的序列,起始於 μ,每次增加一個方格,最後一個是 λ,更精確一點來說,該序列第 i 個分拆是 μ 聯集所有的方格滿足它裏面的數字 ≤i。若 λ/μ 只是半標準的,仍可被視為是一個整數分拆的序列,但每次增加的方格數可能多於一個,根據半標準楊表的定義,在同一行中每次至多增加一個方格,而這個形狀被稱作「水平條」。該序列完全決定了 λ/μ 與各方格填入的數字,所以也有作者以此來當作(半)標準楊表的定義,例如伊恩·G·麥唐諾英語Ian G. Macdonald[3]。此定義包含了 λ、μ 和所有方格中的資訊。

楊表應用的概述

楊表經常應用於在組合學表示理論代數幾何中,各種不同的計算楊表個數的方法給出舒爾函數英語Schur function的定義以及相關的恆等式。此外,許多關於楊表的組合演算法已經被發現了,例如 Schützenberger 提出的 jeu de taquin英語jeu de taquin 以及 RSK 對應英語Robinson–Schensted–Knuth correspondence。Lascoux 和 Schützenberger 研究一個定義在半標準楊表上面的乘積,該乘積滿足結合律,並且給出一個稱為 le monoïde plaxique (法語) 的結構。

在表示理論的應用

一個楊表的表示

給定一個楊表πλ ,一共有n個方格。那麼把1到n這n個數字填到這個楊表中,使得每行從左到右都是遞增的,每列從下到上也是遞增的。用 dimπλ 表示這樣的方法個數,如圖,這個這種填寫數字中的一種。我們有下面的勾長公式。

勾長

一個楊表的勾長

對於楊表中的一個方格v,其勾長 hook(v)等於同行右邊的方格數加上同列上面的方格數,再加上1(也就是他自己)。

勾長公式

用 dimλ表示這樣的方法個數,勾長公式就是方法個數等於n!除以所有方格的勾長的乘積。

對於分拆10 = 5 + 4 + 1 的應的楊表. 因此有

種方法。

參考資料

  1. ^ 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 .
  2. ^ 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. ^ 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).