Young tableau
Young tableau
Main page
Y

Young tableau

logo
Community Hub0 subscribers
Read side by side
Young tableau
View on Wikipedia
from Wikipedia

In mathematics, a Young tableau (/tæˈbloʊ, ˈtæbloʊ/; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups and to study their properties.

Young tableaux were introduced by Alfred Young, a mathematician at Cambridge University, in 1900.[1][2] They were then applied to the study of the symmetric group by Georg Frobenius in 1903. Their theory was further developed by many mathematicians, including Percy MacMahon, W. V. D. Hodge, G. de B. Robinson, Gian-Carlo Rota, Alain Lascoux, Marcel-Paul Schützenberger and Richard P. Stanley.

Definitions

[edit]

Note: this article uses the English convention for displaying Young diagrams and tableaux.

Diagrams

[edit]
Young diagram of shape (5, 4, 1), English notation
Young diagram of shape (5, 4, 1), French notation

A Young diagram (also called a Ferrers diagram, particularly when represented using dots) is a finite collection of boxes, or cells, arranged in left-justified rows, with the row lengths in non-increasing order. Listing the number of boxes in each row gives a partition λ of a non-negative integer n, the total number of boxes of the diagram. The Young diagram is said to be of shape λ, and it carries the same information as that partition. Containment of one Young diagram in another defines a partial ordering on the set of all partitions, which is in fact a lattice structure, known as Young's lattice. Listing the number of boxes of a Young diagram in each column gives another partition, the conjugate or transpose partition of λ; one obtains a Young diagram of that shape by reflecting the original diagram along its main diagonal.

There is almost universal agreement that in labeling boxes of Young diagrams by pairs of integers, the first index selects the row of the diagram, and the second index selects the box within the row. Nevertheless, two distinct conventions exist to display these diagrams, and consequently tableaux: the first places each row below the previous one, the second stacks each row on top of the previous one. Since the former convention is mainly used by Anglophones while the latter is often preferred by Francophones, it is customary to refer to these conventions respectively as the English notation and the French notation; for instance, in his book on symmetric functions, Macdonald advises readers preferring the French convention to "read this book upside down in a mirror" (Macdonald 1979, p. 2). This nomenclature probably started out as jocular. The English notation corresponds to the one universally used for matrices, while the French notation is closer to the convention of Cartesian coordinates; however, French notation differs from that convention by placing the vertical coordinate first. The figure on the right shows, using the English notation, the Young diagram corresponding to the partition (5, 4, 1) of the number 10. The conjugate partition, measuring the column lengths, is (3, 2, 2, 2, 1).

Arm and leg length

[edit]

In many applications, for example when defining Jack functions, it is convenient to define the arm length aλ(s) of a box s as the number of boxes to the right of s in the diagram λ in English notation. Similarly, the leg length lλ(s) is the number of boxes below s. The hook length of a box s is the number of boxes to the right of s or below s in English notation, including the box s itself; in other words, the hook length is aλ(s) + lλ(s) + 1.

Tableaux

[edit]
A standard Young tableau of shape (5, 4, 1): the numbers 1-10 in the boxes increase in every row and every column.

A Young tableau is obtained by filling in the boxes of the Young diagram with symbols taken from some alphabet, which is usually required to be a totally ordered set. Originally that alphabet was a set of indexed variables x1, x2, x3..., but now one usually uses a set of numbers for brevity. In their original application to representations of the symmetric group, Young tableaux have n distinct entries, arbitrarily assigned to boxes of the diagram. A tableau is called standard if the entries in each row and each column are increasing. The number of distinct standard Young tableaux on n entries is given by the involution numbers

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (sequence A000085 in the OEIS).
All standard Young tableaux with at most 5 boxes

In other applications, it is natural to allow the same number to appear more than once (or not at all) in a tableau. A tableau is called semistandard, or column strict, if the entries weakly increase along each row and strictly increase down each column. Recording the number of times each number appears in a tableau gives a sequence known as the weight of the tableau. Thus the standard Young tableaux are precisely the semistandard tableaux of weight (1,1,...,1), which requires every integer up to n to occur exactly once.

In a standard Young tableau, the integer is a descent if appears in a row strictly below . The sum of the descents is called the major index of the tableau.[3]

Variations

[edit]

There are several variations of this definition: for example, in a row-strict tableau the entries strictly increase along the rows and weakly increase down the columns. Also, tableaux with decreasing entries have been considered, notably, in the theory of plane partitions. There are also generalizations such as domino tableaux or ribbon tableaux, in which several boxes may be grouped together before assigning entries to them.

Skew tableaux

[edit]
Skew tableau of shape (5, 4, 2, 2) / (2, 1), English notation

A skew shape is a pair of partitions (λ, μ) such that the Young diagram of λ contains the Young diagram of μ; it is denoted by λ/μ. If λ = (λ1, λ2, ...) and μ = (μ1, μ2, ...), then the containment of diagrams means that μi ≤ λi for all i. The skew diagram of a skew shape λ/μ is the set-theoretic difference of the Young diagrams of λ and μ: the set of squares that belong to the diagram of λ but not to that of μ. A skew tableau of shape λ/μ is obtained by filling the squares of the corresponding skew diagram; such a tableau is semistandard if entries increase weakly along each row, and increase strictly down each column, and it is standard if moreover all numbers from 1 to the number of squares of the skew diagram occur exactly once. While the map from partitions to their Young diagrams is injective, this is not the case for the map from skew shapes to skew diagrams;[4] therefore the shape of a skew diagram cannot always be determined from the set of filled squares only. Although many properties of skew tableaux only depend on the filled squares, some operations defined on them do require explicit knowledge of λ and μ, so it is important that skew tableaux do record this information: two distinct skew tableaux may differ only in their shape, while they occupy the same set of squares, each filled with the same entries.[5] Young tableaux can be identified with skew tableaux in which μ is the empty partition (0) (the unique partition of 0).

Any skew semistandard tableau T of shape λ/μ with positive integer entries gives rise to a sequence of partitions (or Young diagrams), by starting with μ, and taking for the partition i places further in the sequence the one whose diagram is obtained from that of μ by adding all the boxes that contain a value  ≤ i in T; this partition eventually becomes equal to λ. Any pair of successive shapes in such a sequence is a skew shape whose diagram contains at most one box in each column; such shapes are called horizontal strips. This sequence of partitions completely determines T, and it is in fact possible to define (skew) semistandard tableaux as such sequences, as is done by Macdonald (Macdonald 1979, p. 4). This definition incorporates the partitions λ and μ in the data comprising the skew tableau.

Overview of applications

[edit]

Young tableaux have numerous applications in combinatorics, representation theory, and algebraic geometry. Various ways of counting Young tableaux have been explored and lead to the definition of and identities for Schur functions.

Many combinatorial algorithms on tableaux are known, including Schützenberger's jeu de taquin and the Robinson–Schensted–Knuth correspondence. Lascoux and Schützenberger studied an associative product on the set of all semistandard Young tableaux, giving it the structure called the plactic monoid (French: le monoïde plaxique).

In representation theory, standard Young tableaux of size k describe bases in irreducible representations of the symmetric group on k letters. The standard monomial basis in a finite-dimensional irreducible representation of the general linear group GLn are parametrized by the set of semistandard Young tableaux of a fixed shape over the alphabet {1, 2, ..., n}. This has important consequences for invariant theory, starting from the work of Hodge on the homogeneous coordinate ring of the Grassmannian and further explored by Gian-Carlo Rota with collaborators, de Concini and Procesi, and Eisenbud. The Littlewood–Richardson rule describing (among other things) the decomposition of tensor products of irreducible representations of GLn into irreducible components is formulated in terms of certain skew semistandard tableaux.

Applications to algebraic geometry center around Schubert calculus on Grassmannians and flag varieties. Certain important cohomology classes can be represented by Schubert polynomials and described in terms of Young tableaux.

Applications in representation theory

[edit]
See also: Representation theory of the symmetric group

Young diagrams are in one-to-one correspondence with irreducible representations of the symmetric group over the complex numbers. They provide a convenient way of specifying the Young symmetrizers from which the irreducible representations are built. Many facts about a representation can be deduced from the corresponding diagram. Below, we describe two examples: determining the dimension of a representation and restricted representations. In both cases, we will see that some properties of a representation can be determined by using just its diagram. Young tableaux are involved in the use of the symmetric group in quantum chemistry studies of atoms, molecules and solids.[6][7]

Young diagrams also parametrize the irreducible polynomial representations of the general linear group GLn (when they have at most n nonempty rows), or the irreducible representations of the special linear group SLn (when they have at most n − 1 nonempty rows), or the irreducible complex representations of the special unitary group SUn (again when they have at most n − 1 nonempty rows). In these cases semistandard tableaux with entries up to n play a central role, rather than standard tableaux; in particular it is the number of those tableaux that determines the dimension of the representation.

Dimension of a representation

[edit]
Main article: Hook length formula
Hook-lengths of the boxes for the partition 10 = 5 + 4 + 1
Hook-lengths of the boxes for the partition 10 = 5 + 4 + 1

The dimension of the irreducible representation πλ of the symmetric group Sn corresponding to a partition λ of n is equal to the number of different standard Young tableaux that can be obtained from the diagram of the representation. This number can be calculated by the hook length formula.

A hook length hook(x) of a box x in Young diagram Y(λ) of shape λ is the number of boxes that are in the same row to the right of it plus those boxes in the same column below it, plus one (for the box itself). By the hook-length formula, the dimension of an irreducible representation is n! divided by the product of the hook lengths of all boxes in the diagram of the representation:

The figure on the right shows hook-lengths for all boxes in the diagram of the partition 10 = 5 + 4 + 1. Thus

Similarly, the dimension of the irreducible representation W(λ) of GLr corresponding to the partition λ of n (with at most r parts) is the number of semistandard Young tableaux of shape λ (containing only the entries from 1 to r), which is given by the hook-length formula:

where the index i gives the row and j the column of a box.[8] For instance, for the partition (5,4,1) we get as dimension of the corresponding irreducible representation of GL7 (traversing the boxes by rows):

Restricted representations

[edit]

A representation of the symmetric group on n elements, Sn is also a representation of the symmetric group on n − 1 elements, Sn−1. However, an irreducible representation of Sn may not be irreducible for Sn−1. Instead, it may be a direct sum of several representations that are irreducible for Sn−1. These representations are then called the factors of the restricted representation (see also induced representation).

The question of determining this decomposition of the restricted representation of a given irreducible representation of Sn, corresponding to a partition λ of n, is answered as follows. One forms the set of all Young diagrams that can be obtained from the diagram of shape λ by removing just one box (which must be at the end both of its row and of its column); the restricted representation then decomposes as a direct sum of the irreducible representations of Sn−1 corresponding to those diagrams, each occurring exactly once in the sum.

See also

[edit]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Young tableau

View on Grokipedia
from Grokipedia
A Young tableau is a combinatorial structure consisting of a Young diagram—a left-justified array of boxes arranged in rows of nonincreasing length, corresponding to a partition of a positive integer—filled with entries from a totally ordered set such that the entries are weakly increasing along each row from left to right and strictly increasing down each column.[1] The most common variant, known as a standard Young tableau, uses the numbers 1 through n exactly once, with strictly increasing rows and columns, and the number of such tableaux of a given shape is given by the hook-length formula.[1] Semi-standard Young tableaux allow repeated entries that are weakly increasing in rows and strictly increasing in columns, often using entries from 1 to k for some k.[1] Young tableaux were introduced in 1900 by the English mathematician Alfred Young as a tool for studying the representation theory of the symmetric group, where standard Young tableaux index the basis elements via the Young symmetrizer.[2] Beyond their foundational role in symmetric group representations, Young tableaux have broad applications across mathematics, including algebraic combinatorics, where they enumerate objects via the Robinson–Schensted–Knuth correspondence linking permutations to pairs of tableaux; symmetric functions, through the Schur function basis; and algebraic geometry, in the study of Grassmannians and flag varieties.[3] They also appear in probability, via uniform random generation of tableaux, and in statistical mechanics, modeling certain lattice paths and tilings.[3] The versatility of Young tableaux underscores their status as a cornerstone of modern combinatorics and related fields.[3]

Definitions and Fundamentals

Young Diagrams

A Young diagram, also known as a Ferrers diagram in its dot representation, is a left-justified array of boxes arranged in rows of nonincreasing lengths, where the lengths correspond to the parts of an integer partition λ = (λ₁ ≥ λ₂ ≥ ⋯ ≥ λ_k > 0) of a positive integer n, and the i-th row contains exactly λ_i boxes.[4][5] This geometric structure visually encodes the partition by stacking rows such that the total number of boxes equals n, with rows aligned to the left and decreasing in length from top to bottom.[6] The conjugate partition λ' of λ is obtained by transposing the Young diagram, which involves reflecting it over the main diagonal to read the lengths of the columns as the new row lengths.[7] For instance, if λ = (4, 2, 1), the diagram has four boxes in the first row, two in the second, and one in the third; its conjugate λ' = (3, 1, 1, 1) reflects the three boxes in the first column, one in the second, one in the third, and one in the fourth.[7] A partition is self-conjugate if λ = λ', such as λ = (3, 2, 1), where the diagram is symmetric across the diagonal: 
□ □ □
□ □
□
In this example, the column lengths are also 3, 2, and 1.[7] For any cell (i, j) in a Young diagram—where i indexes the row from the top and j the column from the left—the arm length a(i, j) is the number of boxes to the right of (i, j) in row i, and the leg length l(i, j) is the number of boxes below (i, j) in column j.[6] The hook length h(i, j) of the cell is then defined as h(i, j) = a(i, j) + l(i, j) + 1, accounting for the cell itself along with its arm and leg.[6] Continuing the example of λ = (3, 2, 1), the hook lengths for each cell (i, j) are as follows:
(1,1)(1,2)(1,3)
531
31
1
Here, for (1,1): a(1,1) = 2, l(1,1) = 2, h(1,1) = 5; for (2,2): a(2,2) = 0, l(2,2) = 0, h(2,2) = 1.[6] These lengths provide a combinatorial framework for analyzing the diagram's structure.

Young Tableaux

A Young tableau is formed by filling the boxes of a Young diagram with numbers according to specific monotonicity rules, extending the geometric structure of the diagram into a combinatorial object used in various areas of mathematics.[8] A standard Young tableau (SYT) of a given shape λ, where λ is a partition of n (denoted λ ⊢ n), consists of a bijective assignment of the integers 1 through n to the n boxes of the diagram such that the entries are strictly increasing from left to right along each row and from top to bottom along each column.[1] This ensures that each SYT represents a unique way to order the numbers while respecting the partial order imposed by the diagram's rows and columns. For example, the partition λ = (2,1) has two standard Young tableaux: 
1 2
3

1 3
2
In each, the numbers increase strictly across rows and down columns.[1] A semi-standard Young tableau (SSYT) generalizes this by allowing fillings with positive integers (possibly with repetitions), where entries are weakly increasing from left to right along each row (non-decreasing) and strictly increasing from top to bottom along each column.[1] The multiset of entries in an SSYT is often specified by a weight, corresponding to the number of times each integer appears, which connects to applications in symmetric function theory. For the same shape λ = (2,1), an example of an SSYT is: 
1 1
2
Here, the first row has repeated 1's (weakly increasing), while the column has 1 < 2 (strictly increasing).[1][9] Yamanouchi words, also known as lattice words, of shape λ are words of length n over the positive integers with exactly λ_i occurrences of the integer i for each i, such that in every prefix of the word, the number of occurrences of i is at least the number of occurrences of i+1 for each i. This establishes a bijection between standard Young tableaux of shape λ and Yamanouchi words of shape λ, given by the row word: for a tableau T, the k-th letter of the word is the row index containing the entry k in T.[9][8]

Variations

Skew tableaux generalize the concept of Young tableaux by allowing fillings on skew diagrams, which are the boxes of a Young diagram λ\lambda minus the boxes of a subdiagram μ⊂λ\mu \subset \lambda, where λ\lambda and μ\mu are partitions with ∣λ∣−∣μ∣=n|\lambda| - |\mu| = n for tableaux of size nn. A standard skew Young tableau of shape λ/μ\lambda/\mu is a bijective filling of the skew diagram with {1,2,…,n}\{1, 2, \dots, n\} such that entries strictly increase along each row from left to right and along each column from top to bottom.[10] Similarly, a semistandard skew Young tableau of shape λ/μ\lambda/\mu fills the diagram with positive integers that are weakly increasing in rows and strictly increasing in columns, allowing repetitions but unbounded from above.[11] Reverse plane partitions extend the filling rules further by relaxing the strictness and bijectivity requirements. A reverse plane partition of shape λ\lambda is a filling of the Young diagram λ\lambda with non-negative integers that are weakly increasing along rows from left to right and along columns from top to bottom, with no upper bound on entries and repetitions permitted. This contrasts with standard plane partitions, which are weakly decreasing in both directions, but reverse versions arise naturally in generating functions and symmetric function theory. Plane partitions serve as three-dimensional analogs to Young tableaux, representing stacked layers of boxes in the positive octant that form a stable pile, equivalent to a finite subset of Z≥03\mathbb{Z}_{\geq 0}^3 satisfying a stability condition where no box floats without support from below or to the side.[12] These can be visualized as a Young diagram in each horizontal slice, with heights constrained by the partition shape, effectively generalizing two-dimensional tableaux to a boxed, multi-layered structure. For example, consider the skew shape (3,2)/(1)(3,2)/(1), which consists of four boxes: positions (1,2)(1,2), (1,3)(1,3), (2,1)(2,1), and (2,2)(2,2). One standard skew Young tableau filling is: 
  1  2
3  4
where the first row has entries in columns 2 and 3, and the second row in columns 1 and 2; entries increase in rows (1 < 2, 3 < 4) and columns (1 < 4 in column 2). Another valid filling is: 
  2  4
1  3
satisfying the same increasing conditions.[10] Affine or cylindric variations further extend skew tableaux to infinite or periodic settings, such as cylindric tableaux, which are infinite skew tableaux periodic with period (k,m)(k,m), repeating rows every kk steps downward while shifting mm positions left, identifying corresponding entries on the cylinder.[13]

Combinatorial Properties

Hook-Length Formula

The hook-length formula provides an explicit product formula for the number fλf^\lambda of standard Young tableaux of a given shape λ⊢n\lambda \vdash n, where λ\lambda is a partition of the integer nn. For a cell (i,j)(i,j) in the Young diagram of λ\lambda, the hook length h(i,j)h(i,j) is the number of cells to the right of (i,j)(i,j) in row ii, plus the number of cells below (i,j)(i,j) in column jj, plus one for the cell itself. The formula states that
fλ=n!∏(i,j)∈λh(i,j). f^\lambda = \frac{n!}{\prod_{(i,j) \in \lambda} h(i,j)}.
This formula was discovered in 1954 by Frame, Robinson, and Thrall as part of their study of representations of the symmetric group via hook graphs. Several proofs of the hook-length formula exist, including probabilistic and bijective approaches that outline its derivation without requiring a full inductive verification. One probabilistic proof, due to Greene, Nijenhuis, and Wilf, models the uniform random filling of the diagram with numbers 1 through nn and uses a "hook walk" process to show that the probability of obtaining a standard Young tableau equals the reciprocal of the product of hook lengths. Another derivation employs a modified jeu de taquin operation to establish a bijection between standard Young tableaux and certain lattice paths or growth diagrams, directly yielding the hook-length product.[14] To illustrate, consider the shape λ=(2,1)⊢3\lambda = (2,1) \vdash 3. The hook lengths are h(1,1)=3h(1,1) = 3 (right:1, below:1, plus 1), h(1,2)=1h(1,2) = 1, and h(2,1)=1h(2,1) = 1. Thus,
f(2,1)=3!3⋅1⋅1=2. f^{(2,1)} = \frac{3!}{3 \cdot 1 \cdot 1} = 2.
The two standard Young tableaux are
\begin{ytableau} *(lightgray) 1 & 3 \\ 2 \end{ytableau} \qquad \text{and} \qquad \begin{ytableau} *(lightgray) 1 & 2 \\ 3 \end{ytableau}.
The following table lists fλf^\lambda for all partitions of small n≤5n \leq 5, computed via the hook-length formula:
nnλ\lambdafλf^\lambda
1(1)1
2(2)1
(1,1)1
3(3)1
(2,1)2
(1^3)1
4(4)1
(3,1)3
(2,2)2
(2,1,1)3
(1^4)1
5(5)1
(4,1)4
(3,2)5
(3,1,1)6
(2,2,1)5
(2,1^3)6
(1^5)1
A generalization of the hook-length formula exists for the number of standard Young tableaux of skew shape λ/μ\lambda / \mu, though it involves a more complex product over excited diagrams rather than a simple hook product.[15]

RSK Correspondence

The Robinson–Schensted–Knuth (RSK) correspondence is a fundamental bijection in combinatorics that associates permutations in the symmetric group SnS_n with pairs of standard Young tableaux (P,Q)(P, Q) of the same shape, where PP is the insertion tableau and QQ is the recording tableau.[16] This correspondence was first introduced by G. de B. Robinson in 1938 as a method to decompose the regular representation of the symmetric group using tableaux, though without a full bijective proof.[16] It was rediscovered and rigorously established as a bijection by C. Schensted in 1961, who connected it to the lengths of longest increasing and decreasing subsequences in permutations. In 1970, D. E. Knuth generalized the algorithm to non-negative integer matrices, yielding a bijection with pairs of semistandard Young tableaux (SSYT) of the same shape, and introduced relations characterizing equivalence classes of inputs that produce the same output shape. Central to the RSK correspondence is Schensted insertion, an algorithm for building the insertion tableau PP while maintaining the increasing properties of rows and columns. To insert a number xx into an existing Young tableau, begin with the first row: place xx in the leftmost position where it is smaller than the entry to its right, displacing (or "bumping") that entry to the next row; if no such position exists, append xx to the end of the row. The bumped entry then repeats the process in the subsequent row, continuing until an entry is appended to the end of some row, which adds a new box to the shape. This ensures the resulting tableau remains row- and column-strictly increasing. For a permutation σ∈Sn\sigma \in S_n viewed as the sequence σ(1),σ(2),…,σ(n)\sigma(1), \sigma(2), \dots, \sigma(n), the insertion tableau PP is obtained by successively inserting these values using Schensted insertion, starting from an empty tableau; simultaneously, the recording tableau QQ is built by placing the index ii (from 1 to nn) in the new box added at the ii-th step, ensuring both PP and QQ are standard Young tableaux of the same shape λ⊢n\lambda \vdash n. The map is bijective, with the inverse recovered via reverse bumping or jeu de taquin procedures. For example, consider the permutation 231, given by the sequence 2, 3, 1. Inserting 2 yields P=(2)P = (2). Inserting 3 appends to the first row, giving P=(2,3)P = (2, 3). Inserting 1 into (2, 3) bumps 2 (the leftmost entry >1), resulting in first row (1, 3) and second row (2), so P=(1,3∣2)P = (1, 3 | 2). The recording tableau QQ records the steps: 1 at the first box, 2 at the second box in the first row, and 3 at the new box in the second row, yielding Q=(1,2∣3)Q = (1, 2 | 3). The inverse process recovers the original sequence 2, 3, 1 from (P,Q)(P, Q). Knuth's 1970 extension generalizes the correspondence to m×nm \times n matrices with non-negative integer entries, associating each such matrix with a pair (P,Q)(P, Q) of SSYT of the same shape, where entries in rows are weakly increasing and in columns strictly increasing. The algorithm processes the matrix column by column (or row by row in variants), inserting each entry via a generalized Schensted insertion that allows equal entries without bumping. Two-line arrays (with top row strictly increasing and bottom row arbitrary non-negative integers) map to such pairs, and the shape is preserved under Knuth equivalence classes: two arrays are equivalent if one can be obtained from the other by a sequence of Knuth relations, such as swapping adjacent entries (i,j+1∣k,l)(i, j+1 | k, l) with i<k≤j<li < k \leq j < l or similar transpositions that do not change the resulting tableaux pair. These relations define the plactic monoid structure underlying the correspondence.

Applications in Algebra and Representation Theory

Schur Polynomials

Schur polynomials provide a fundamental connection between the combinatorics of Young tableaux and the algebra of symmetric functions. For a partition λ\lambda and variables x1,…,xmx_1, \dots, x_m, the Schur polynomial sλ(x1,…,xm)s_\lambda(x_1, \dots, x_m) is defined as the sum over all semistandard Young tableaux TT of shape λ\lambda with entries from {1,…,m}\{1, \dots, m\}, of the monomial ∏i=1mxici(T)\prod_{i=1}^m x_i^{c_i(T)}, where ci(T)c_i(T) denotes the multiplicity of ii in TT.[17] This combinatorial definition leverages semistandard Young tableaux, which feature weakly increasing rows and strictly increasing columns, to generate a homogeneous symmetric polynomial of degree ∣λ∣|\lambda|.[17] Key properties of Schur polynomials highlight their role in representation theory. They serve as the characters of the irreducible representations of the symmetric group SnS_n indexed by λ⊢n\lambda \vdash n, where the character value on a conjugacy class corresponding to partition μ\mu is obtained by evaluating the Schur polynomial appropriately.[17] Additionally, Schur polynomials form an orthonormal basis for the ring of symmetric functions with respect to the Hall inner product, ensuring ⟨sλ,sμ⟩=δλμ\langle s_\lambda, s_\mu \rangle = \delta_{\lambda \mu}.[18] The Pieri rule provides a basic multiplication formula: sλhk=∑sμs_\lambda h_k = \sum s_\mu, where the sum is over partitions μ\mu such that μ/λ\mu / \lambda is a horizontal strip of kk boxes.[19] The Jacobi-Trudi identity offers an alternative generating function expression for Schur polynomials in terms of complete homogeneous symmetric polynomials hkh_k. Specifically,
sλ=det⁡(hλi+j−i)1≤i,j≤ℓ(λ), s_\lambda = \det \left( h_{\lambda_i + j - i} \right)_{1 \leq i,j \leq \ell(\lambda)},
where ℓ(λ)\ell(\lambda) is the length of λ\lambda, and h0=1h_0 = 1 with hk=0h_k = 0 for k<0k < 0.[20] This determinant form underscores their structural role within symmetric function theory. For example, consider λ=(2,1)\lambda = (2,1) and variables x,y,zx, y, z. The semistandard Young tableaux of this shape yield
s(2,1)(x,y,z)=x2y+x2z+xy2+y2z+xz2+yz2+2xyz. s_{(2,1)}(x,y,z) = x^2 y + x^2 z + x y^2 + y^2 z + x z^2 + y z^2 + 2 x y z.
The terms arise from fillings like 1 in first row both, 2 below contributing x2yx^2 y, and permutations thereof, with the coefficient 2 for xyzx y z from tableaux such as 1 2 / 3 and 1 3 / 2.[17] In the context of general linear group representations, Schur polynomials characterize the irreducible polynomial representations of GL(m,C)\mathrm{GL}(m, \mathbb{C}). The representation corresponding to highest weight λ\lambda (with ℓ(λ)≤m\ell(\lambda) \leq m) has character sλ(x1,…,xm)s_\lambda(x_1, \dots, x_m) on the torus of diagonal matrices with eigenvalues x1,…,xmx_1, \dots, x_m, linking the combinatorial sum to the highest weight vector's orbit.[21]

Representations of Symmetric Groups

The irreducible representations of the symmetric group SnS_n over the complex numbers are in one-to-one correspondence with the partitions λ⊢n\lambda \vdash n, where each partition λ\lambda labels a unique irreducible representation known as the Specht module VλV^\lambda.1 These modules provide a combinatorial framework for understanding the representation theory of SnS_n, with Young tableaux serving as the key tool for constructing bases and computing invariants. The Specht modules were first constructed by Wilhelm Specht in 1935, building on earlier work by Alfred Young that linked tableaux to group representations.2 The Specht module VλV^\lambda is defined as a submodule of the permutation module MλM^\lambda, which has basis given by the tabloids {t}\{t\} formed by equivalence classes of Young tableaux of shape λ\lambda under row permutations.1 Specifically, VλV^\lambda is spanned by the polytabloids et=∑σ∈Ctsgn⁡(σ)σ{t}e_t = \sum_{\sigma \in C_t} \operatorname{sgn}(\sigma) \sigma \{t\}, where CtC_t is the column stabilizer group of the tableau tt, and a standard basis consists of polytabloids ete_t for standard Young tableaux (SYT) tt of shape λ\lambda.3 The group SnS_n acts on VλV^\lambda by permuting the entries in the tableaux, with σ⋅et=eσt\sigma \cdot e_t = e_{\sigma t}, preserving the submodule structure.1 These modules are irreducible, and they exhaust all irreducible representations of SnS_n, providing a complete classification parameterized by Young diagrams.3 The dimension of VλV^\lambda is given by dim⁡Vλ=fλ\dim V^\lambda = f^\lambda, the number of standard Young tableaux of shape λ\lambda.1 This quantity fλf^\lambda can be computed using the hook-length formula, which counts SYT via products over hook lengths in the diagram.4 The dimensions satisfy the orthogonality relation ∑λ⊢n(dim⁡Vλ)2=n!\sum_{\lambda \vdash n} (\dim V^\lambda)^2 = n!, reflecting the decomposition of the regular representation of SnS_n.1 The character χλ\chi^\lambda of the representation VλV^\lambda evaluates on a permutation σ∈Sn\sigma \in S_n as χλ(σ)\chi^\lambda(\sigma), which counts certain fixed points or can be computed combinatorially.1 One method uses the Robinson-Schensted-Knuth (RSK) correspondence, where χλ(σ)\chi^\lambda(\sigma) relates to the number of pairs of tableaux of shape λ\lambda arising from the insertion and recording of σ\sigma.5 Alternatively, the Murnaghan-Nakayama rule provides a recursive formula: χλ(ρ)=∑(−1)ht(R)−1χλ−R(ρ′)\chi^\lambda(\rho) = \sum (-1)^{ht(R)-1} \chi^{\lambda - R}(\rho'), summing over rim hooks RR of length equal to a part of the cycle type of ρ\rho, where ht(R)ht(R) is the height of the hook.67 For n=3n=3, the partitions are (3)(3), (2,1)(2,1), and (13)(1^3), corresponding to the trivial representation (dim⁡=1\dim=1), the standard representation (dim⁡=2\dim=2), and the sign representation (dim⁡=1\dim=1), respectively.1 The two SYT of shape (2,1)(2,1) are: 
1 2
3
and 
1 3
2
These basis elements generate the 2-dimensional Specht module under the S3S_3-action.3

Branching Rules and Dimensions

In the representation theory of the symmetric group $ S_n $, the irreducible representation $ V^\lambda $ corresponding to a partition $ \lambda \vdash n $ restricts to the subgroup $ S_{n-1} $ via Young's branching rule, decomposing as a direct sum of irreducible representations $ V^\mu $ where each $ \mu $ is obtained by removing a single removable box from the Young diagram of $ \lambda $. A removable box is one at the end of a row such that the resulting shape remains a valid partition, and this decomposition is multiplicity-free, with each $ V^\mu $ appearing exactly once. The multiplicity can also be understood combinatorially through the number of standard Young tableaux (SYT) of shape $ \mu $ that can be extended to shape $ \lambda $ by adding numbers appropriately, or via paths in the Young lattice from $ \mu $ to $ \lambda $. For example, consider the partition $ \lambda = (2,1) \vdash 3 $, corresponding to the standard representation of $ S_3 $ of dimension 2. Removing a removable box from the diagram yields either $ \mu = (2) $ (the trivial representation of $ S_2 $) or $ \mu = (1,1) $ (the sign representation of $ S_2 $), so $ V^{(2,1)} \downarrow_{S_2} \cong V^{(2)} \oplus V^{(1,1)} $, each of dimension 1. This illustrates how addible and removable boxes determine the branching structure, with the number of removable boxes giving the number of summands. Induction from a product subgroup $ S_k \times S_{n-k} $ to $ S_n $ decomposes the induced representation $ \operatorname{Ind}{S_k \times S{n-k}}^{S_n} (V^\mu \otimes V^\nu) $ into irreducibles $ V^\lambda $ with multiplicity given by the Littlewood-Richardson coefficient $ c^\lambda_{\mu \nu} $, which counts the number of semistandard Young tableaux (SSYT) of skew shape $ \lambda / \mu $ with content $ \nu $. This coefficient provides the branching multiplicity for such inductions but is distinct from the single-box case for $ S_{n-1} $. Dimensions of these representations and their branches are computed using the hook-length formula, which gives $ \dim V^\lambda = n! / \prod_{(i,j) \in \lambda} h_{(i,j)} $, where $ h_{(i,j)} $ is the hook length at position $ (i,j) $ in the diagram of $ \lambda $. For the restricted representation $ V^\lambda \downarrow_{S_{n-1}} $, the dimension is the sum of $ \dim V^\mu $ over all removable $ \mu $. An adaptation of the Weyl character formula for symmetric groups, via the Schur polynomial $ s_\lambda(1^n) = \dim V^\lambda $, extends to branching by evaluating characters on subgroup classes, though the hook formula suffices for explicit computation in these cases. Yamanouchi chains provide a combinatorial framework for identifying highest weight vectors in $ V^\lambda $, consisting of chains of partitions $ \emptyset = \lambda^{(0)} \subset \lambda^{(1)} \subset \cdots \subset \lambda^{(n)} = \lambda $ in the Young lattice, where each consecutive pair differs by adding one box, and the associated reading word is a Yamanouchi word—satisfying the condition that in every prefix, the number of 1's is at least the number of 2's, and so on for higher integers. These chains label an orthogonal basis for the Specht module where the Jucys-Murphy elements act diagonally, facilitating computations of branching multiplicities and highest weights corresponding to the partition $ \lambda $. For instance, in the representation $ V^{(2,1)} $, the Yamanouchi chains correspond to paths adding boxes in orders that maintain the lattice word property, aligning with the highest weight vector under the standard embedding into GL representations.[22]

Further Applications and Generalizations

Littlewood-Richardson Rule

The Littlewood–Richardson rule gives a combinatorial description of the coefficients arising in the decomposition of the tensor product of two irreducible polynomial representations of the general linear group GL(n,C)\mathrm{GL}(n, \mathbb{C}), or equivalently, in the product of two Schur functions. For partitions λ,ν,μ\lambda, \nu, \mu with ∣λ∣+∣ν∣=∣μ∣|\lambda| + |\nu| = |\mu|, the multiplicity of the irreducible representation VμV_\mu in Vλ⊗VνV_\lambda \otimes V_\nu is the Littlewood–Richardson coefficient cλνμc^\mu_{\lambda \nu}, which equals the number of Littlewood–Richardson tableaux of skew shape μ/λ\mu / \lambda and content ν\nu.[23] These coefficients also appear as the structure constants in the ring of symmetric functions under multiplication of Schur functions: sλsν=∑μcλνμsμs_\lambda s_\nu = \sum_\mu c^\mu_{\lambda \nu} s_\mu.[24] A semi-standard Young tableau (SSYT) of skew shape μ/λ\mu / \lambda and content ν\nu fills the boxes of the skew diagram μ/λ\mu / \lambda with positive integers such that the integer ii appears exactly νi\nu_i times, entries are weakly increasing along rows from left to right, and strictly increasing down columns.[23] Such an SSYT is a Littlewood–Richardson tableau if its reverse reading word—formed by reading the entries in each row of the skew diagram from right to left, proceeding from the top row to the bottom—is a Yamanouchi word. A word is Yamanouchi if, for every prefix, the number of occurrences of each integer ii is at least the number of occurrences of i+1i+1, for all i≥1i \geq 1.[24] This lattice condition ensures the tableau corresponds to a valid decomposition pathway in the representation tensor product.[23] The rule also incorporates the property that no two identical entries appear in the same column of the skew filling, though this is already enforced by the strict column increase in SSYT; the Yamanouchi condition further guarantees the lattice property of the overall content.[24] To count the coefficients or verify a given filling, one can employ an algorithmic approach using Schützenberger's jeu de taquin, which involves iteratively sliding entries in the skew tableau to "straighten" it into a straight shape; a valid Littlewood–Richardson tableau rectifies under reverse jeu de taquin to a semi-standard Young tableau of shape ν\nu whose content matches the evaluation requirements.[24] For example, consider the tensor product V(1,1)⊗V(1)V_{(1,1)} \otimes V_{(1)}, where the partitions indicate representations of total degree 3. The decomposition is V(1,1)⊗V(1)=V(2,1)⊕V(1,1,1)V_{(1,1)} \otimes V_{(1)} = V_{(2,1)} \oplus V_{(1,1,1)}, with each multiplicity equal to 1. For c(1,1),(1)(2,1)c^{(2,1)}_{(1,1),(1)}, the skew shape (2,1)/(1,1)(2,1)/(1,1) consists of a single box at position (1,2); filling it with 1 yields the SSYT
\begin{ytableau} *(lightgray) & 1 \\ *(lightgray) & \\ \end{ytableau}
whose reverse reading word is "1", a Yamanouchi word. Similarly, for c(1,1),(1)(1,1,1)c^{(1,1,1)}_{(1,1),(1)}, the skew shape (1,1,1)/(1,1)(1,1,1)/(1,1) is a single box at (3,1), filled with 1:
\begin{ytableau} *(lightgray) \\ *(lightgray) \\ 1 \end{ytableau}
with reverse reading word "1", also Yamanouchi. These explicit fillings confirm the multiplicities.[23] The Littlewood–Richardson rule extends briefly to plethysm computations, where certain plethystic products like sλ(sν)s_\lambda(s_\nu) can be expressed using counts of iterated Littlewood–Richardson tableaux, though full plethysms require more involved combinatorial models.[24]

Plane Partitions and Extensions

Plane partitions generalize Young diagrams to three dimensions, representing them as stacks of boxes forming a solid Young diagram where parts are nonincreasing along rows, columns, and heights, often confined within bounding boxes such as an a×b×ca \times b \times c rectangular prism.[25] These structures, introduced by MacMahon in the early 20th century, extend the combinatorial framework of partitions by allowing a third dimension of descent, and their enumeration involves generating functions that refine classical counts by statistics like volume or trace. A key refinement is the qq-analog of the hook-length formula, which counts plane partitions inside a box by weighting them according to certain path interpretations or major index analogs, as developed by Macdonald in the context of symmetric functions.[26] For instance, the generating function for plane partitions in an a×b×ca \times b \times c box is given by a product formula involving qq-hook lengths, providing a qq-deformation that interpolates between the number of such partitions at q=1q=1 and weighted enumerations. A concrete example is a plane partition fitting inside a 2×2×22 \times 2 \times 2 box, visualized as a 2×22 \times 2 array of nonnegative integers at most 2, nonincreasing across rows and down columns:
∣2110∣ \begin{vmatrix} 2 & 1 \\ 1 & 0 \end{vmatrix}
This corresponds to a solid diagram with heights 2, 1 in the first row and 1, 0 in the second, totaling volume 4, and satisfies the descent conditions while respecting the box bounds.[25] In statistical mechanics, plane partitions and related Young tableaux appear in mappings to integrable lattice models, particularly the six-vertex model, where configurations of nonintersecting paths (vicious walkers) biject to oscillating or osculating tableaux, encoding domain-wall boundary conditions and phase transitions.[27] These correspondences allow exact computations of partition functions via determinantal formulas, linking combinatorial growth of tableaux shapes to arctic curves and fluctuation phenomena in the model.[27] Young tableaux also serve as crystal graphs in the representation theory of quantum groups, specifically realizing the crystal bases of irreducible highest-weight modules for Uq(sln)U_q(\mathfrak{sl}_n), where vertices are semistandard tableaux and edges are defined by Kashiwara operators e~i\tilde{e}_i and f~i\tilde{f}_i that raise or lower the content by adding or removing boxes while preserving the Yamanouchi property or signature rules.[28] These operators act by scanning rows and columns for ii and i+1i+1 entries, effectively crystalizing the qq-deformed enveloping algebra and enabling combinatorial tracking of tensor product decompositions without explicit weights.[28] For a simple example in the fundamental representation of Uq(sl3)U_q(\mathfrak{sl}_3), consider the highest-weight tableau with a single box labeled 1; applying the lowering operator f~2\tilde{f}_2 yields the empty tableau (annihilating it), while f~1\tilde{f}_1 yields the tableau with a single box labeled 2, illustrating the crystal's Dynkin diagram structure.[28] Beyond these, the RSK correspondence extends Young tableaux to applications in sorting networks, where reduced decompositions of permutations biject to pairs of staircase-shaped tableaux, facilitating analysis of parallel sorting algorithms and their probabilistic limits.[29] In random matrix theory, the length of the longest increasing subsequence in a random permutation, encoded as the first row length of the RSK insertion tableau, follows the Tracy-Widom distribution in the large-nn limit, mirroring eigenvalue spacing statistics of Gaussian unitary ensembles and bridging combinatorics with Dyson’s Brownian motion.[30]

References

  1. Young Tableau -- from Wolfram MathWorld
  2. [PDF] The Ubiquitous Young Tableau - Michigan State University
  3. Alfred Young - Biography - MacTutor - University of St Andrews
  4. [math/0611030] What is a Young tableau? - arXiv
  5. Young Diagram -- from Wolfram MathWorld
  6. Ferrers Diagram -- from Wolfram MathWorld
  7. [PDF] 18.212 S19 Algebraic Combinatorics, Lecture 3: Pattern avoidance ...
  8. Self-Conjugate Partition -- from Wolfram MathWorld
  9. Enumerative Combinatorics
  10. Partitions, permutations and tableaux - symmetric functions
  11. [PDF] Bottom Schur functions - MIT Mathematics
  12. [PDF] An algorithmic Littlewood-Richardson rule - arXiv
  13. [PDF] arXiv:0802.3948v2 [math.CO] 2 Jul 2008
  14. [PDF] Cylindric Young Tableaux and their Properties
  15. [PDF] A direct bijective proof of the hook-length formula
  16. [PDF] Hook-length formulas for skew shapes - arXiv
  17. On the Representations of the Symmetric Group - jstor
  18. [PDF] Schur Polynomials and the Irreducible Representations of Sn
  19. [PDF] notes for math 740 (symmetric functions)
  20. [PDF] An introduction to Schur polynomials
  21. [PDF] The theory of Schur polynomials revisited - UMD MATH
  22. None
  23. [PDF] On subgroup adapted bases for representations of the symmetric ...
  24. Littlewood–Richardson coefficients - symmetric functions
  25. [PDF] The Littlewood-Richardson rule, and related combinatorics - arXiv
  26. [PDF] The Shape of a Typical Boxed Plane Partition
  27. https://www-math.mit.edu/~rstan/pubs/pubfiles/75.pdf
  28. [math/0701755] Osculating Paths and Oscillating Tableaux - arXiv
  29. [q-alg/9706025] Crystal Bases and Young Tableaux - arXiv
  30. [PDF] Sorting networks, staircase Young tableaux, and last passage ...
  31. [PDF] longest increasing subsequences: - from patience sorting to the
User Avatar
No comments yet.