Young Tableau

Introduction

Young tableau, also called a Young table, is a combinatorial object commonly used in representation theory and Schubert calculus.

A Young tableau is a special kind of matrix. It facilitates the study of 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. It studies abstract algebraic structures by representing their elements as linear transformations of vector spaces. Schubert calculus is a branch of algebraic geometry, introduced by Hermann Schubert in the 19th century to solve counting problems in projective geometry.

Definition

Young diagram

A Young diagram (also called a Ferrers diagram when dots are used to represent it; see the section on integer partitions for more information) is a finite collection of boxes or cells, left-aligned, with row lengths in non-increasing order. If we list the number of squares in each row of a Young diagram, we obtain an integer partition $n$ (the total number of squares) $\lambda$. Thus, we can regard the shape of a Young diagram as $\lambda$, since it carries the same information as its integer partition.

The inclusion relation between Young diagrams defines a partial order on integer partitions. This relation has the structure of a lattice, called Young's lattice. If we list the number of squares in each column of a Young diagram, we obtain the "conjugate partition" or "transpose partition" of the integer partition $\lambda$. The corresponding Young diagram can be obtained by reflecting the original Young diagram across its main diagonal.

The position of each square in a Young diagram is determined by two coordinates representing the row number and column number, respectively. Columns are ordered from left to right, while rows are ordered in the direction from more squares to fewer squares. Here, it is important to note that there are two different conventions for drawing Young diagrams: in the first, rows with fewer squares are placed below rows with more squares; in the second, the rows are stacked upward, one layer at a time, from largest to smallest. Since the former convention is used mainly in English-speaking countries, while the latter is usually used in French-speaking countries, they are conventionally called the English and French conventions, respectively.

The following table shows the two conventions for drawing the Young diagram corresponding to the integer partition $(5,4,1)$:

• English convention:

  

• French convention:

  

Young tableau

Definition

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

When Young tableaux were first applied to the representation theory of symmetric groups, the $n$ squares of a Young diagram could be filled arbitrarily with distinct positive integers from $1$ to $n$. Most research today, however, uses "standard" Young tableaux, in which the numbers in the boxes of each row and each column are strictly increasing. The number of distinct Young tableaux with $n$ squares forms the involution number:

Note

The involution number (or telephone number) is an integer sequence in mathematics that counts the number of ways to connect $n$ telephone lines to one another, with each line connected to at most one other line. It can also describe the number of matchings in a complete graph with $n$ vertices, the number of permutations of $n$ elements that are involutions, the sum of the absolute values of the coefficients of a Hermite polynomial, the number of standard Young tableaux with $n$ cells, and the sum of the degrees of the irreducible representations of a symmetric group.

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

In other applications, Young diagrams may also be filled with repeated numbers. If the numbers in each column are strictly increasing and the numbers in each row are non-decreasing, the resulting Young tableau is called semistandard (Semistandard Young Tableaux, sometimes called column-strict). Recording the number of times each number appears in a Young tableau gives a sequence regarded as the weight of the Young tableau. Therefore, the weight of a standard Young tableau must be $(1,1,\ldots,1)$, because each positive integer from $1$ to $n$ appears exactly once in a standard Young tableau.

Insertion algorithm for standard Young tableaux

The properties of permutations can be illustrated intuitively 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$ to mean inserting $x$ into the Young tableau starting from the first row, as follows:

1. In the current row, find the smallest number $y$ that is greater than $x$.
2. If one is found, replace $y$ with $x$, move to the next row, set $x \leftarrow y$, and repeat step 1.
3. If none is found, put $x$ at the end of the row and exit. Suppose that $x$ is in row $s$ and 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)$ is a cell.

For example, the steps for inserting $3$ into the Young tableau $(2, 5, 9)(6, 7)(8)$ are:

Variants

There are many variants of Young tableaux that are not fully strict standard tableaux (Variations). For example, row-strict Young tableaux require the numbers in each row to be strictly increasing and the numbers in each column to be non-decreasing; they are the conjugates of column-strict Young tableaux. In addition, in the theory of plane partitions, it is customary to replace increasing with decreasing in the definition above. Other variants, such as set-valued Young tableaux, first package some boxes into groups and then require all boxes in each group to be filled with the same number.

Skew tableaux

Given two Young diagrams $\lambda = (\lambda{1}, \lambda{2} \ldots)$ and $\mu = (\mu{1}, \mu{2},\ldots)$ satisfying that $\lambda$ contains $\mu$, that is, $\mu{i} \leq \mu{i}$ for every $i$, define the "skew Young diagram" $\lambda/\mu$ as all squares in $\lambda$ minus all squares in $\mu$, that is, the set difference $\lambda$ minus $\mu$. Filling the cells of a skew Young diagram with elements forms a skew tableau (Skew tableaux).

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

Similarly, if the numbers in each column are strictly increasing and the numbers in each row are non-decreasing, the skew tableau is called a semistandard skew tableau; if a semistandard skew tableau is filled with the distinct numbers $1$ to $n$ (the total number of cells), it is called a standard skew tableau. Note that different $\lambda$ and $\mu$ can yield the same $\lambda/\mu$. Although most properties of skew tableaux depend only on the cells remaining after taking the set difference, some operations still depend on the choice of $\lambda$ and $\mu$. Therefore, $\lambda/\mu$ must be regarded as containing two pieces of information: $\lambda$ and $\mu$. When $\mu$ is the empty partition (the unique partition of $0$), the skew 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 yield 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 it with the $n$ numbers from $1$ to $n$ so that the numbers increase from left to right in each row and from bottom to top in each column. Let $dim_{\pi_{\lambda}}$ denote the number of ways to perform such a filling.

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

Hook length formula

If $dim_{\lambda}$ denotes the number of such fillings, the hook length formula states that this number 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)}}.$$

Therefore, for the Young tableau of the integer partition $10 = 5 + 4 + 1$, as shown above, we have

$$\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.

Examples

Subsequence problem

For a Young tableau $P$, consider a permutation $X = x_{1}, \ldots , x_{n}$ of the numbers from $1$ to $n$.

1. The length of the first row in $P_{X}$ is the length of the longest increasing subsequence (LIS) of the permutation $X$. Note that the first row of $P$ is not necessarily the LIS itself, so properties of Young tableaux cannot be used directly to solve problems such as "LIS partitioning".

2. For a permutation $X$ and the Young tableau $P_{X}$ it produces, if $X^R$ is the reversal of $X$, then the Young tableau $P_{X^R}$ produced by $X^R$ is obtained by transposing $P_{X}$.

   For example, for the 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 in the Young tableau $P_{X}$ is the length of the longest decreasing subsequence (LDS) of the permutation $X$.

Define the length of an $LIS/LDS$ with length no more than $k$ as $k-LIS$ and $k-LDS$, respectively. Such problems can likewise 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 also 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 the permutation $X^∗$ be $(P_{m,1}\ldots,P_{m,λ_{m}},P_{m−1,1}\ldots,P_{1,1}\ldots P_{1,λ_{1}})$ (that is, write the rows of the Young tableau one after another from bottom to top). Then $X$ can always be transformed into $X^*$ by swap operations.

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

CTSC2017 Longest Increasing Subsequence

Given 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}$, and suppose that the length of $C$'s longest increasing subsequence is at most $k$. Find the maximum possible length of $C$.

Solution idea

For multiple queries, consider using a scanline method. We then need to maintain the Young tableau of every prefix. Using the conclusion above, the problem becomes how to efficiently maintain the sum of the lengths of the first $k$ columns of the Young tableau. Maintaining it directly has complexity $O(n^2 \log n)$, which is unacceptable. Consider maintaining the first $\sqrt{n}$ columns and the first $\sqrt{n}$ rows.

It can be seen that the Young tableau will never completely cover this $W \times H$ rectangle. If $K \leq W$, the answer can be obtained directly; if $K > W$, the part greater than $W$ must lie within the $H$ rows. Thus, we can consider maintaining the first $\sqrt{n}$ columns and the first $\sqrt{n}$ rows simultaneously. Reversing this permutation gives the transpose of the Young tableau, so it is only necessary to maintain $-A_{i}$ simultaneously as well, with complexity $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 Dominoes

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)$. 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 drawn in this histogram.

References and further reading

1. Young Tableau - from Wolfram MathWorld
2. Young tableau - Wikipedia
3. Hook length formula - Wikipedia
4. Fangzhou Yuan, "An Introduction to the Applications of Young Matrices in Informatics Competitions" IOI2019, Proceedings of the Chinese National Team Candidate Papers, 202-229