跳转至

楊氏矩陣

引入

楊氏矩陣(Young tableau)，又名楊表，是一種常用於表示論和舒伯特演算中的組合對象。

楊表是一種特殊的矩陣。它便於對稱羣和一般線性羣的羣表示和性質研究。楊表由劍橋大學數學家阿爾弗雷德·楊（Alfred Young）於 1900 年首次提出，於 1903 年被德國數學家弗羅貝尼烏斯（Ferdinand Georg Frobenius）應用於對稱羣的研究。

註釋

表示論（Representation theory）是數學的一個分支。它通過將元素表示為向量空間的線性變換來研究抽象代數結構。舒伯特演算（Schubert calculus）是代數幾何的一個分支，於 19 世紀由赫爾曼·舒伯特為了解決射影幾何的計數問題而引入。

定義

楊圖

楊圖（Young diagram，使用點表示時又稱 Ferrers 圖，在 分拆數 一節中有相關介紹）是一個有限的框或單元格集合，左對齊排列，行長按非遞增順序排列。如果把楊圖每行的方格數列出，我們得到了一個非負整數 \(n\)（總方格數）的 整數分拆(integer partition)\(\lambda\)。因此，我們可以將楊圖的形狀看作 \(\lambda\)，因為它攜帶與其整數拆分相同的信息。

楊圖之間的包含關係定義了整數分拆上的一個 偏序 關係，此關係擁有 格 的結構，被稱為 楊格(Young's lattice)。如果把楊圖各列的方格數列出，則會得到整數分拆 \(\lambda\) 的「共軛分拆」，或「轉置分拆」，它所對應到的楊圖可由原本的楊圖沿主對角線作鏡射對稱而得。

楊圖每個方格的位置由分別代表 行數 與 列數 的兩個座標點決定。列的順序由左向右，行的順序則按方格數的由多向少的方向。此處需要注意，根據習慣不同存在着兩種不同的楊圖畫法：第一個將方格數較少的行排在方格數較多的行的下方，第二種畫法將各行由大到小一層一層往上疊。由於前一種畫法主要由英語國家使用，而後者通常被法語國家使用，習慣上我們分別稱它們為英式畫法和法式畫法。

以下表格中分別為整數分拆 \((5,4,1)\) 對應的楊圖不同畫法：

  • 英式畫法：
  • 法式畫法：

楊表

定義

楊表（Young tableau）是通過用取自某個字母表的符號填充楊氏圖的框來獲得的，這通常需要是一個全序集和。填入的元素寫作 \(x_{1}\),\(x_{2}\),\(x_{3}\),\(\ldots\)。但為了方便起見，都直接填入正整數。

楊表最初應用於對稱羣的表示理論時，允許在楊圖的 \(n\) 的方格中任意填入 \(1\) 到 \(n\) 中相異的正整數。但現在的研究大多使用「標準」的楊表，即上述條件中各行與各列中方格的數字皆為嚴格遞增的。由 \(n\) 個方格的相異楊表數個數形成 對和數：

註釋

對和數（involution number/telephone number）是在數學中是一個整數序列，用來計算 \(n\) 條電話線中每條線路最多可以連接到另一條線路時可以相互連接的方法個數。它還可以用來描述完全圖 \(n\) 個頂點上的匹配數，\(n\) 個對合元素的排列數，Hermite 多項式係數的絕對值之和，含有 \(n\) 個格子的標準楊表的個數，以及不可約對稱羣的度數之和。

\(1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, \ldots\)（OEIS 中的數列 A000085）

在其他應用中，楊圖也可以被填入相同的數字。若填法的同列數字嚴格遞增，且同行數字單調遞增，則該楊表被稱為是 半標準的（Semistandard Young Tableaux, 有時稱為列嚴格）。楊表中個數字出現的次數記錄下來得到的序列被視為楊表的 權重。因此，標準楊表的權重必然是 \((1,1,\ldots,1)\)。因為在標準楊表中，\(1\) 到 \(n\) 的每個正整數恰好各出現一次。

標準楊表的插入算法

排列的性質可以由楊表直觀地表現出來。RSK 插入算法 就提供了一個將楊表和排列聯繫起來的途徑。它由 Robinson, Schensted 和 Knuth 提出。

令 \(S\) 是一個楊表，定義 \(S \leftarrow x\) 表示將 \(x\) 從第一行插入楊表中，具體如下：

  1. 在當前行中找到最小的比 \(x\) 大的數 \(y\)。
  2. 如果找到了，用 \(x\) 去替換 \(y\)，移到下一行，令 \(x \leftarrow y\) 重複操作 1。
  3. 如果找不到，就把 \(x\) 放在該行末尾並退出。記 \(x\) 在第 \(s\) 行第 \(t\) 列，\((s, t)\) 必定是一個邊角。一個格子 \((s, t)\) 是邊角當且僅當 \((s + 1, t)\) 和 \((s, t + 1)\) 都不存在格子。

例如，將 \(3\) 插入楊表 \((2, 5, 9)(6, 7)(8)\) 的步驟為：

變體

非完全嚴格標準的楊表有許多變體（Variations）。例如行嚴格楊表要求同行數字嚴格遞增，且同列數字單調遞增，即列嚴格楊表的共軛。此外，在平面分拆（plane partitions）理論中，習慣上會將上述的定義中的遞增改為遞減。其他變體例如帶狀楊表，會先將一些方塊打包成羣，然後要求各羣的方塊必須填入相同數字。

斜楊表

給定兩個楊圖 \(\lambda = (\lambda{1}, \lambda{2} \ldots)\)、\(\mu = (\mu{1}, \mu{2},\ldots)\)，滿足 \(\lambda\) 包含 \(\mu\)，即 \(\mu{i} \leq \mu{i}\) 對所有 \(i\)。定義「斜楊圖」\(\lambda/\mu\) 為 \(\lambda\) 中所有方格減去 \(\mu\) 中的所有方格 即 \(\lambda\) 差集 \(\mu\)。在斜楊圖的各方格中填入元素就形成了 斜楊表(Skew tableaux)。

例如，下圖為整數分拆 \((5,4,1)\) 對應的一個標準斜楊表：

同理，若滿足同一列中的數字嚴格遞增，且同一行中的數字單調遞增，則該斜楊表被稱作 半標準斜楊表；若半標準斜楊表滿足各方格不重複的填入數字 \(1\) 到 \(n\)（方格總數），則該斜楊表被稱作 標準斜楊表。注意，由不同的 \(\lambda\) 和 \(\mu\) 可得到相同的 \(\lambda/\mu\)。雖然大部分斜楊表的性質都只依賴於取完差集的方格，但是仍然部分運算依賴於 \(\lambda\) 和 \(\mu\) 的選取。因此，\(\lambda/\mu\) 必須被視為包含兩個元素信息：\(\lambda\) 和 \(\mu\)。當 \(\mu\) 是空分拆（\(0\) 的唯一一種分拆）時，斜楊表 \(\lambda/\mu\) 就變成楊表 \(\lambda\)。

應用

楊表常用於在組合學、表示理論和代數幾何中，用各種不同計算楊表個數的方法得到舒爾函數的定義及相關的恆等式。在信息學競賽中，常有考察楊表鈎長公式的題目。

勾長

給定一個共有 \(n\) 個方格的楊表 \(\pi_{\lambda}\)，把 \(1\) 到 \(n\) 的 \(n\) 個數字填入楊表中，使得每行從左到右，每列從下到上都是遞增的。用 \(dim_{\pi_{\lambda}}\) 表示可以這樣填的方法個數。

對於楊表中的一個方格 \(v\)，定義其 勾長 \(\mathrm{hook}(v)\) 等於同行右邊的方格數加上同列上面的方格數，再加 1（即方格本身）。

勾長公式

如果用 \(dim_{\lambda}\) 表示這樣的方法個數，勾長公式 就是方法個數等於 \(n!\) 除以所有方格的勾長的乘積。

\[ \dim \pi _{\lambda}={\frac {n!}{\prod_{{x\in Y(\lambda)}}{\mathrm {hook}}(x)}}. \]

所以對於整數分拆 \(10 = 5 + 4 + 1\) 的楊表，如上圖所示。有

\[ \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. \]

種方法。

例題

子序列問題

對於楊表 \(P\), 定義對於一個從 \(1\) 到 \(n\) 的排列 \(X = x_{1}, \ldots , x_{n}\)。

  1. \(P_{X}\) 中第一行的長度即為排列 \(X\) 的 最長上升子序列（LIS） 長度。注意，\(P\) 的第一行並不一定是 LIS 本身，所以不能直接利用楊表性質解決「LIS 劃分」之類的問題。

  2. 對於一個排列 \(X\) 和它產生的楊表 \(P_{X}\)，若 \(X^R\) 是 \(X\) 的翻轉，那麼 \(X^R\) 產生的楊表 \(P_{X^R}\) 即為 \(P_{X}\) 交換行列得到。

    例如，對於排列 \(X = 1, 5, 7, 2, 8, 6, 3, 4\) 和 \(X^R = 4, 3, 6, 8, 2, 7, 5, 1\), 我們可得到如下楊表 \(P_{X}\):

  3. 楊表 \(P_{X}\) 中的第一列長度即為排列 \(X\) 的 最長下降子序列（LDS） 長度。

定義長度不超過 \(k\) 的 \(LIS/LDS\) 長度為 \(k-LIS\) 和 \(k-LDS\), 此類問題我們同樣可以用楊表來解決。對於 \(1-LIS\)，顯而易見最長的 \(1-LIS\) 子序列就是該序列的 \(LDS\)，這也正是楊表的第一列；同樣可得，楊表前 \(k\) 列的長度就是最長的 \(k-LIS\) 子序列的長度。證明如下：

對於一個排列 \(X\) 和它的 \(m\) 行楊表 \(P\)，令排列 \(X^∗\) 為 \((P_{m,1}\ldots,P_{m,λ_{m}},P_{m−1,1}\ldots,P_{1,1}\ldots P_{1,λ_{1}})\)（即將楊表從下往上每行依次寫在後面）。那麼 \(X\) 一定可以通過交換操作轉化成 \(X^*\)。

所以，最長 \(k-LIS\) 子序列長度可以表示成 \(F(k)=\sum_{i=1}^{m} \min(k,\lambda_{i})\)，即前 \(k\) 列的長度和。

CTSC2017 最長上升子序列

有一個長為 \(n\) 的數列 \(b\)。對於序列 \(B_{m} = (b_{1}, b_{2},\ldots, b_{m})\)，設 \(C\) 是 \(B_{m}\) 的子序列，且 \(C\) 的最長上升子序列的長度不超過 \(k\)，詢問 \(C\) 的長度最大值。

解題思路

多個詢問考慮使用掃描線的方法。這樣我們就需要維護每個前綴的楊表。如果使用以上結論，可以發現問題變成了如何快速維護楊表前 \(k\) 列的長度之和。如果直接維護，複雜度是 \(O(n^2 \log n)\) 的不能接受。考慮維護前 \(\sqrt{n}\) 列和前 \(\sqrt{n}\) 行。

可以發現，楊表一定不會完全覆蓋這個 \(W \times H\) 的矩形。如果 \(K \leq W\)，那麼可以直接得答案；如果 \(K > W\)，那麼大於 \(W\) 的部分一定在 \(H\) 行內。所以可以考慮如何同時維護前 \(\sqrt{n}\) 列和前 \(\sqrt{n}\) 行。將這個排列翻轉一下就可以得到楊表的翻轉，所以只需要再同時維護 \(-A_{i}\) 即可，複雜度為 \(O(n \sqrt{n} \log n)\)。

BJWC2018 最長上升子序列

現在有一個長度為 \(n\) 的隨機排列，求它的最長上升子序列長度的期望。

CF1268B 楊氏多米諾骨牌

給定一個具有 \(n\) 列長度 \(a_{1} ,a_{2},\ldots,a_{n}\,(a_{1} \geq a_{2} \geq \ldots \geq a_{n} \geq 1)\) 的直方圖。\(a=[3,2,2,2,1]\) 的楊圖。找到可以在此直方圖中繪製的最大數量的非重疊多米諾骨牌（\(1 \times 2\) 或 \(2 \times 1\) 矩形）。

參考資料與拓展閲讀

  1. Young Tableau - from Wolfram MathWorld
  2. Young tableau - Wikipedia
  3. Hook length formula - Wikipedia
  4. 袁方舟，《淺談楊氏矩陣在信息學競賽中的應用》IOI2019, 中國國家候選隊論文集，202-229
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用