Young Tableau

Introduction

Young tableau, also known as Young tableaux, is a combinatorial object frequently used in representation theory and Schubert calculus.

A Young tableau is a special kind of matrix. It facilitates the study of group representations and properties of symmetric groups and general linear groups. Young tableaux were first introduced in 1900 by the Cambridge mathematician Alfred Young and were applied to the study of symmetric groups in 1903 by the German mathematician Ferdinand Georg Frobenius.

Note

Representation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces. Schubert calculus is a branch of algebraic geometry introduced in the 19^th century by Hermann Schubert to solve counting problems in projective geometry.

Definition

Young Diagram

A Young diagram (also called a Ferrers diagram when represented with dots, see the section on Ferrers diagrams in the partition number article) is a finite collection of boxes or cells, left-aligned, with row lengths in non-increasing order. If we list the number of cells in each row of a Young diagram, we obtain an integer partition \(\lambda\) of a non-negative integer \(n\) (the total number of cells). Therefore, we can view the shape of a Young diagram as \(\lambda\), as it carries the same information as its integer partition.

The inclusion relation among Young diagrams defines a partial order on integer partitions. This relation possesses the structure of a lattice and is called Young's lattice. If we list the number of cells in each column of a Young diagram, we obtain the "conjugate partition" or "transpose partition" of \(\lambda\). The corresponding Young diagram can be obtained by reflecting the original Young diagram along the main diagonal.

The position of each cell in a Young diagram is determined by two coordinates representing the row number and column number. Columns are ordered from left to right, and rows are ordered from the row with the most cells to the row with the fewest cells. Note that there are two different conventions for drawing Young diagrams based on different habits: the first places rows with fewer cells below rows with more cells, while the second stacks rows from largest to smallest, layer by layer from bottom to top. Since the former is primarily used in English-speaking countries and the latter is typically used in French-speaking countries, they are conventionally called the English notation and the French notation, respectively.

The following table shows the different drawings of the Young diagram corresponding to the integer partition \((5,4,1)\):

• English notation:
• French notation:

Young Tableau

Definition

A Young tableau is obtained by filling the boxes of a Young diagram with symbols from some alphabet, which usually needs to be a totally ordered set. The filled elements are written as \(x_{1}\), \(x_{2}\), \(x_{3}\), \(\ldots\). For convenience, positive integers are often used directly.

When Young tableaux were first applied to the representation theory of symmetric groups, it was allowed to fill the \(n\) cells of the Young diagram with distinct positive integers from \(1\) to \(n\). However, most current research uses "standard" Young tableaux, where the numbers in each row and each column of the above conditions are strictly increasing. The number of distinct Young tableaux with \(n\) cells forms the involution numbers:

Note

Involution numbers (also known as telephone numbers) are an integer sequence in mathematics that counts the number of ways \(n\) telephone lines can be connected to each other, with each line connected to at most one other line. They can also be used to describe the number of matchings on a complete graph with \(n\) vertices, the number of permutations with \(n\) involutions, the sum of absolute values of Hermite polynomial coefficients, the number of standard Young tableaux with \(n\) cells, and the sum of degrees of irreducible symmetric groups.

\(1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, \ldots\) (Sequence A000085 in the OEIS)

In other applications, Young diagrams can also be filled with identical numbers. If the filling method has strictly increasing numbers in each column and monotonically increasing numbers in each row, the Young tableau is called semistandard (Semistandard Young Tableaux, sometimes called column-strict). The sequence obtained by recording the number of occurrences of each number in the Young tableau is considered the weight of the Young tableau. Therefore, the weight of a standard Young tableau must be \((1,1,\ldots,1)\), because in a standard Young tableau, each positive integer from \(1\) to \(n\) appears exactly once.

Insertion Algorithm for Standard Young Tableaux

The properties of permutations can be intuitively represented by Young tableaux. The RSK insertion algorithm provides a way to connect Young tableaux and permutations. It was proposed by Robinson, Schensted, and Knuth.

Let \(S\) be a Young tableau. Define \(S \leftarrow x\) as inserting \(x\) into the Young tableau starting from the first row, as follows:

1. In the current row, find the smallest number \(y\) greater than \(x\).
2. If found, replace \(y\) with \(x\), move to the next row, set \(x \leftarrow y\), and repeat step 1.
3. If not found, place \(x\) at the end of the row and exit. Record that \(x\) is at row \(s\), column \(t\). \((s, t)\) must be a corner. A cell \((s, t)\) is a corner if and only if neither \((s + 1, t)\) nor \((s, t + 1)\) exists.

For example, the steps to insert \(3\) into the Young tableau \((2, 5, 9)(6, 7)(8)\) are:

Variations

There are many variations of non-fully strict standard Young tableaux. For example, row-strict Young tableaux require strictly increasing numbers in each row and monotonically increasing numbers in each column, i.e., the conjugate of column-strict Young tableaux. Additionally, in the theory of plane partitions, it is customary to change the increasing condition in the above definition to decreasing. Other variations, such as ribbon Young tableaux, first pack some cells into groups and then require that cells in the same group must be filled with the same number.

Skew Young Tableaux

Given two Young diagrams \(\lambda = (\lambda_{1}, \lambda_{2} \ldots)\) and \(\mu = (\mu_{1}, \mu_{2},\ldots)\), satisfying that \(\lambda\) contains \(\mu\), i.e., \(\mu_{i} \leq \lambda_{i}\) for all \(i\). Define the "skew Young diagram" \(\lambda/\mu\) as all cells in \(\lambda\) minus all cells in \(\mu\), i.e., the set difference \(\lambda \setminus \mu\). Filling the cells of a skew Young diagram with elements forms a skew Young tableau.

For example, the following figure shows a standard skew Young tableau corresponding to the integer partition \((5,4,1)\):

Similarly, if the numbers in the same column are strictly increasing and the numbers in the same row are monotonically increasing, the skew Young tableau is called a semistandard skew Young tableau; if a semistandard skew Young tableau satisfies that the cells are filled with distinct numbers from \(1\) to \(n\) (the total number of cells), it is called a standard skew Young tableau. Note that different \(\lambda\) and \(\mu\) can yield the same \(\lambda/\mu\). Although most properties of skew Young tableaux depend only on the cells after taking the difference, some operations still depend on the choice of \(\lambda\) and \(\mu\). Therefore, \(\lambda/\mu\) must be considered as containing information about both elements: \(\lambda\) and \(\mu\). When \(\mu\) is the empty partition (the only partition of \(0\)), the skew Young tableau \(\lambda/\mu\) becomes the Young tableau \(\lambda\).

Applications

Young tableaux are commonly used in combinatorics, representation theory, and algebraic geometry. Various methods for counting Young tableaux lead to the definition of Schur functions and related identities. In informatics competitions, problems often test the hook length formula for Young tableaux.

Hook Length

Given a Young tableau \(\pi_{\lambda}\) with a total of \(n\) cells, fill the \(n\) numbers from \(1\) to \(n\) into the Young tableau such that each row is increasing from left to right and each column is increasing from bottom to top. Let \(dim_{\pi_{\lambda}}\) denote the number of ways to fill it.

For a cell \(v\) in the Young tableau, define its hook length \(\mathrm{hook}(v)\) as the number of cells to the right in the same row plus the number of cells above in the same column, plus 1 (the cell itself).

Hook Length Formula

If \(dim_{\lambda}\) denotes the number of such ways, the hook length formula states that the number of ways equals \(n!\) divided by the product of the hook lengths of all cells.

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

Thus, for the Young tableau of the integer partition \(10 = 5 + 4 + 1\), as shown in the figure above, there are

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

ways.

Example Problems

Subsequence Problems

For a Young tableau \(P\), define for a permutation \(X = x_{1}, \ldots , x_{n}\) from \(1\) to \(n\):

1. The length of the first row of \(P_{X}\) is the length of the Longest Increasing Subsequence (LIS) of permutation \(X\). Note that the first row of \(P\) is not necessarily the LIS itself, so properties of Young tableaux cannot be directly used to solve problems like "LIS partitioning".

2. For a permutation \(X\) and the Young tableau \(P_{X}\) it generates, if \(X^R\) is the reverse of \(X\), then the Young tableau \(P_{X^R}\) generated by \(X^R\) is obtained by swapping the rows and columns of \(P_{X}\).

   For example, for permutations \(X = 1, 5, 7, 2, 8, 6, 3, 4\) and \(X^R = 4, 3, 6, 8, 2, 7, 5, 1\), we obtain the following Young tableau \(P_{X}\):

   

3. The length of the first column of the Young tableau \(P_{X}\) is the length of the Longest Decreasing Subsequence (LDS) of permutation \(X\).

Define the length of LIS/LDS not exceeding \(k\) as \(k\)-LIS and \(k\)-LDS. Such problems can also be solved using Young tableaux. For \(1\)-LIS, it is obvious that the longest \(1\)-LIS subsequence is the LDS of the sequence, which is exactly the first column of the Young tableau; similarly, the length of the first \(k\) columns of the Young tableau is the length of the longest \(k\)-LIS subsequence. The proof is as follows:

For a permutation \(X\) and its \(m\)-row Young tableau \(P\), let permutation \(X^*\) be \((P_{m,1}\ldots,P_{m,\lambda_{m}},P_{m−1,1}\ldots,P_{1,1}\ldots P_{1,\lambda_{1}})\) (i.e., writing the Young tableau from bottom to top, row by row, concatenated). Then \(X\) can be transformed into \(X^*\) through swap operations.

Therefore, the length of the longest \(k\)-LIS subsequence can be expressed as \(F(k)=\sum_{i=1}^{m} \min(k,\lambda_{i})\), i.e., the sum of the lengths of the first \(k\) columns.

CTSC2017 Longest Increasing Subsequence

There is a sequence \(b\) of length \(n\). For the sequence \(B_{m} = (b_{1}, b_{2},\ldots, b_{m})\), let \(C\) be a subsequence of \(B_{m}\) such that the length of the longest increasing subsequence of \(C\) does not exceed \(k\). Find the maximum possible length of \(C\).

Solution Idea

For multiple queries, consider using a scanning line approach. This requires maintaining the Young tableau for each prefix. Using the above conclusion, the problem reduces to how to quickly maintain the sum of the lengths of the first \(k\) columns of the Young tableau. Direct maintenance has a complexity of \(O(n^2 \log n)\), which is unacceptable. Consider maintaining the first \(\sqrt{n}\) columns and the first \(\sqrt{n}\) rows.

It can be observed that the Young tableau will never completely cover a \(W \times H\) rectangle. If \(K \leq W\), the answer can be directly obtained; if \(K > W\), the part greater than \(W\) must be within the \(H\) rows. Therefore, consider how to simultaneously maintain the first \(\sqrt{n}\) columns and the first \(\sqrt{n}\) rows. By flipping the permutation, the transpose of the Young tableau can be obtained, so it is only necessary to also maintain \(-A_{i}\). The complexity is \(O(n \sqrt{n} \log n)\).

BJWC2018 Longest Increasing Subsequence

Given a random permutation of length \(n\), find the expected length of its longest increasing subsequence.

CF1268B Young Table

Given a histogram with \(n\) columns of lengths \(a_{1}, a_{2},\ldots,a_{n}\,(a_{1} \geq a_{2} \geq \ldots \geq a_{n} \geq 1)\). For example, the Young diagram for \(a=[3,2,2,2,1]\). Find the maximum number of non-overlapping dominoes (\(1 \times 2\) or \(2 \times 1\) rectangles) that can be placed in this histogram.

References and Further Reading

1. Young Tableau - from Wolfram MathWorld
2. Young tableau - Wikipedia
3. Hook length formula - Wikipedia
4. Yuan Fangzhou, "A Brief Discussion on the Application of Young Tableaux in Informatics Competitions" IOI2019, China National Team Papers, 202-229

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用