Young diagram and tableau

Intuition [Beginner]

A Young diagram is the simplest possible mathematical object: a stack of left-justified rows of boxes, with the rows getting weakly shorter as you go down. The diagram for the partition $\lambda =(4,3,1)$ has a top row of $4$ boxes, a middle row of $3$, and a bottom row of $1$. The partition is the list of row lengths; the diagram is the picture.

Once you draw the diagram, you can fill the boxes with numbers $1,2,\dots ,n$ (where $n$ is the total number of boxes). A filling is called a Young tableau. If the numbers strictly increase along each row and each column, the tableau is called standard; if they only weakly increase along rows but strictly along columns, it is called semistandard.

Why bother with these little pictures? Because they form the combinatorial backbone of the entire representation theory of the symmetric group, and beyond it of the general linear group, the unitary group, and the orthogonal group. Counting tableaux gives dimensions of irreducible representations; building operators from tableaux gives the representations themselves. Alfred Young, working as a Cambridge-educated parish priest in rural England between 1900 and 1934, discovered that everything one needs to know about how the symmetric group breaks into irreducibles is encoded in these stacks of boxes.

Visual [Beginner]

The Young diagram of $\lambda =(4,3,1)$ is three rows of boxes: $4$ boxes on top, $3$ in the middle, $1$ on the bottom, all left-justified. A filling with $1$ through $8$ that strictly increases along rows and columns is a standard Young tableau.

Worked example [Beginner]

Take the partition $\lambda =(3,2)$ of $5$. Its Young diagram has $5$ boxes total: $3$ on top, $2$ on bottom. How many ways are there to fill the boxes with $\{1,2,3,4,5\}$ so that rows increase left-to-right and columns increase top-to-bottom?

Place $1$ in the top-left (forced — it must be in the upper-left corner). Then $5$ must end up in the rightmost top-row cell or the rightmost bottom-row cell (the two outer corners). Working through the cases gives exactly five standard tableaux:

$$\begin{array}{ccc}1& 2& 3\\ 4& 5& \end{array}\begin{array}{ccc}1& 2& 4\\ 3& 5& \end{array}\begin{array}{ccc}1& 2& 5\\ 3& 4& \end{array}\begin{array}{ccc}1& 3& 4\\ 2& 5& \end{array}\begin{array}{ccc}1& 3& 5\\ 2& 4& \end{array}$$

So there are $5$ standard Young tableaux of shape $(3,2)$. What this tells us: this count of standard tableaux equals the dimension of the irreducible representation $V^{(3,2)}$ of $S_5$ — exactly the number predicted by the hook length formula. Tableaux are the basis of the representation.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Definition (Partition and Young diagram). A partition of $n$ is a non-increasing sequence of positive integers

$$\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k),{\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_k\ge 1,|\lambda |:={\lambda }_1+\cdots +{\lambda }_k=n.$$

Write $\lambda ⊢n$ and call $k=\ell (\lambda )$ the length of $\lambda$. The Young diagram of $\lambda$ is the set of cells

$$[\lambda ]:=\{(i,j)\in {\mathbb{Z}}^2:1\le i\le k,1\le j\le {\lambda }_i\},$$

drawn as a left-justified array of boxes. The conjugate (or transpose) partition ${\lambda }^{\prime }$ is obtained by reflecting the diagram across the main diagonal: ${\lambda }_j^{\prime }$ is the length of column $j$.

Definition (Young tableau). A Young tableau of shape $\lambda$ is a filling $T:[\lambda ]\to {\mathbb{Z}}_{\ge 1}$ assigning a positive integer to each cell.

• $T$ is a standard Young tableau (SYT) if it uses each of $1,2,\dots ,n$ exactly once, strictly increasing along rows and strictly increasing down columns. Write $\mathrm{SYT}(\lambda )$ for the set of standard tableaux of shape $\lambda$, with $f^{\lambda }:=|\mathrm{SYT}(\lambda )|$.
• $T$ is a semistandard Young tableau (SSYT) of shape $\lambda$ and content $\mu =({\mu }_1,{\mu }_2,\dots )$ if entry $i$ appears ${\mu }_i$ times, weakly increasing along rows and strictly increasing down columns.

Hook length formula (Frame-Robinson-Thrall, 1954). For a cell $(i,j)\in [\lambda ]$, the hook $H(i,j)$ consists of the cell itself, all cells to its right in row $i$, and all cells below it in column $j$. The hook length $h(i,j):=|H(i,j)|$. Then

$$f^{\lambda }=\frac{n!}{{\prod }_{(i,j)\in [\lambda ]}h(i,j)}.$$

This number equals the dimension of the irreducible $S_n$-representation $V^{\lambda }$ from 07.05.01.

Young symmetriser (after Young 1901). Pick any standard tableau $T$ of shape $\lambda$. Define the row stabiliser $R(T)\subseteq S_n$ as the subgroup of permutations preserving the row sets of $T$, and the column stabiliser $C(T)$ similarly. The Young symmetriser is

$$c_{\lambda }:=\left(\sum _{p\in R(T)}p\right)\left(\sum _{q\in C(T)}\mathrm{sgn}(q)q\right)\in \mathbb{C}[S_n].$$

The element $c_{\lambda }$ is quasi-idempotent ($c_{\lambda }^2$ is a non-zero scalar multiple of $c_{\lambda }$), and its image $\mathbb{C}[S_n]\cdot c_{\lambda }$ realises the irreducible $V^{\lambda }$. Different choices of $T$ give isomorphic representations.

Schur polynomials. For each partition $\lambda$, define the Schur polynomial in variables $x_1,\dots ,x_d$ by

$$s_{\lambda }(x_1,\dots ,x_d):=\sum _{T\in \mathrm{SSYT}(\lambda ,d)}{x}^T,$$

where $\mathrm{SSYT}(\lambda ,d)$ denotes semistandard tableaux of shape $\lambda$ with entries in $\{1,\dots ,d\}$, and $x^T={\prod }_{(i,j)\in \lambda }{x}_{T(i,j)}$. The Schur polynomial is symmetric in $x_1,\dots ,x_d$, and the family $\{s_{\lambda }{\}}_{\ell (\lambda )\le d}$ is a $\mathbb{Z}$-basis of the ring of symmetric polynomials.

Counterexamples to common slips.

• A standard Young tableau is not the same as a semistandard one — standard requires strict increase in both directions and a fixed content $(1,1,\dots ,1)$; semistandard allows repeats in rows.
• The hook length is not simply the row length plus the column length — it counts cells in the actual hook (right + below + the cell itself), not the full row and column.
• A Young diagram drawn with ${\lambda }_i$ rows in increasing order rather than decreasing is sometimes called the "French convention" with the bottom-left corner anchored; the standard "English convention" anchors at the top-left and stacks rows decreasing downward. Either is valid; consistency matters.

Key theorem with proof [Intermediate+]

Theorem (Hook length formula). For any partition $\lambda ⊢n$, the number of standard Young tableaux of shape $\lambda$ equals $n!$ divided by the product of all hook lengths:

$$f^{\lambda }=\frac{n!}{{\prod }_{(i,j)\in [\lambda ]}h(i,j)}.$$

Proof (Greene-Nijenhuis-Wilf 1979 hook walk).

The probabilistic proof of Greene-Nijenhuis-Wilf produces a uniformly random standard tableau by a sequence of hook walks. We sketch it.

Hook walk. Pick a cell $(i,j)\in [\lambda ]$ uniformly at random (probability $1/n$). At each step, move uniformly at random to another cell in the current cell's hook (excluding the current cell itself). Continue until the walk reaches a corner cell — a cell whose hook is just itself. Place $n$ in that corner cell, delete the corner, and recurse on the smaller diagram with $n-1$ cells, placing $n-1,n-2,\dots ,1$ in succession.

Probability claim. The probability that the walk terminates at a particular corner $c$, given the diagram $\lambda$, equals

$$P(c\mid \lambda )=\frac{{\prod }_{(i,j)\in [\lambda \setminus c]}{h}_{\lambda \setminus c}(i,j)}{{\prod }_{(i,j)\in [\lambda ]}{h}_{\lambda }(i,j)}\cdot \frac{n!}{(n-1)!}=\frac{f^{\lambda \setminus c}}{f^{\lambda }}\cdot \frac{n!/H_{\lambda }}{(n-1)!/H_{\lambda \setminus c}}.$$

Inductively assuming the formula $f^{\mu }=(n-1)!/H_{\mu }$ for $\mu ⊢n-1$ (the diagram $\lambda \setminus c$), the recursion shows that placing $n$ at corner $c$ produces every SYT of shape $\lambda$ with exactly the right uniform distribution. Summing over corners $c$, the total probability is $1$, which forces

$$\sum _{c\text{ corner}}\frac{f^{\lambda \setminus c}}{f^{\lambda }}=1,f^{\lambda }=\sum _c{f}^{\lambda \setminus c}=\frac{n!}{H_{\lambda }},$$

closing the induction. $\square$

The original Frame-Robinson-Thrall proof uses determinantal manipulation of the Frobenius character formula; Novelli-Pak-Stoyanovskii (1997) give a fully bijective proof; the Greene-Nijenhuis-Wilf hook walk is the most conceptually transparent. All three converge on the same formula. ^{[Fulton Young Tableaux; Sagan The Symmetric Group; Fulton-Harris §4; Stanley EC Vol II]}

Bridge. The construction here builds toward later units of the strand, where the same pattern is taken up at higher structure. The defining pattern appears again in those units in a sharpened form, where the local data is glued or quotiented. Putting these together, the foundational insight is that the data of this unit gives the structural signature that the rest of the strand reads off.

Exercises [Intermediate+]

Lean formalization [Intermediate+]

lean_status: partial — Mathlib has Combinatorics.Young.YoungDiagram (Young diagrams as combinatorial objects) and Combinatorics.Young.SemistandardYoungTableau. The full hook length formula and its connection to symmetric-group representations are not yet formalised.

[object Promise]

Advanced results [Master]

Hook length formula (combinatorial). Beyond the symmetric-group dimension formula, the hook length formula computes:

• The dimension of skew Specht modules $S^{\lambda /\mu }$ via the skew hook length formula (Naruse 2014).
• $q$-analogues: the principal specialisation $s_{\lambda }(1,q,q^2,\dots ,q^{d-1})$ has a hook content product formula (Stanley); the Hall-Littlewood and Macdonald analogues admit similar product formulas.
• Plancherel measure on partitions: $P(\lambda )=(f^{\lambda }{)}^2/n!$ for $\lambda ⊢n$ defines a probability measure relevant to longest-increasing-subsequence problems and random matrix theory.

Robinson-Schensted-Knuth correspondence. A bijection $S_n\leftrightarrow {⨆}_{\lambda }\mathrm{SYT}(\lambda )\times \mathrm{SYT}(\lambda )$ implementable by row insertion; extends to two-line arrays $\leftrightarrow$ pairs of semistandard tableaux of the same shape. Generates bijective proofs of the Cauchy identity, Plancherel duality, and orthogonality of Schur polynomials. Curiously, RSK has a crystal-theoretic interpretation (Kashiwara): the insertion algorithm corresponds to the action of crystal operators on tensor products.

Plancherel measure asymptotics. Under Plancherel measure on partitions of $n$, the rescaled shape of a typical $\lambda ⊢n$ converges to the Vershik-Kerov-Logan-Shepp limit shape (1977), and the lengths of the first few rows scale as $\sqrt{n}$. Baik-Deift-Johansson (1999) showed that the rescaled fluctuations of the first row converge to the Tracy-Widom distribution from random matrix theory, establishing a deep link between symmetric-group combinatorics and the GUE eigenvalue distribution.

Crystal bases (Kashiwara 1990s). Each polynomial representation of ${\mathrm{GL}}_d$ has a crystal basis indexed by semistandard tableaux. The crystal operators ${\tilde{e}}_i,{\tilde{f}}_i$ act on tableaux by combinatorial moves, providing a "skeleton" of the representation in the limit $q\to 0$ in the quantum group $U_q({\mathfrak{gl}}_d)$. RSK is the crystal isomorphism between $V^{\otimes n}$ and the highest-weight crystal.

Schubert calculus. The cohomology ring of the Grassmannian $\mathrm{Gr}(k,n)$ has a basis of Schubert classes ${\sigma }_{\lambda }$ indexed by partitions $\lambda$ inscribed in a $k\times (n-k)$ rectangle, and the multiplication ${\sigma }_{\mu }\cdot {\sigma }_{\nu }=\sum c_{\mu \nu }^{\lambda }{\sigma }_{\lambda }$ is governed by the Littlewood-Richardson coefficients. The Saturation Conjecture (Knutson-Tao 1999, proved via honeycombs) concerns when LR coefficients are non-zero; Klyachko's solution of Horn's conjecture identifies the cone of valid eigenvalue triples for sums of Hermitian matrices via LR coefficient saturation.

Donaldson-Thomas / Hilbert schemes. The Hilbert scheme of points ${\mathrm{Hilb}}^n({\mathbb{C}}^2)$ has a torus-fixed-point set indexed by partitions of $n$. Nakajima's work on Heisenberg algebras acting on the cohomology of Hilbert schemes uses the partition combinatorics directly.

Synthesis. This construction generalises the pattern fixed in 07.05.01 (symmetric group representation), with the symmetric data replaced by its skew or twisted analogue. Read in the opposite direction, the construction is dual to the metric story: complements and orthogonality are taken with respect to the bilinear datum of this unit, not a metric, and the resulting category of subobjects is the one the rest of the strand classifies. The central insight is that this datum identifies algebra with geometry: functions become vector fields, subspaces become quotients, and invariants become cohomology classes — and that identification is the engine driving every theorem downstream.

Full proof set [Master]

The hook length formula has at least four conceptually distinct proofs: (1) original Frame-Robinson-Thrall via determinantal manipulation of the Frobenius character formula (1954); (2) Greene-Nijenhuis-Wilf hook walk (1979), the probabilistic proof sketched in the Key theorem section; (3) Novelli-Pak-Stoyanovskii fully bijective proof (1997); (4) Naruse's $q$-analogue derivation (2014). All are presented in Sagan The Symmetric Group (with the original FRT proof) and Stanley EC II §7.21 (with the GNW proof and the bijective approach). The RSK correspondence and its extension to skew shapes is in Stanley §7.11-§7.13. The Littlewood-Richardson rule has been proved in many ways: Schützenberger's jeu de taquin (1977), Berenstein-Zelevinsky honeycombs (Knutson-Tao 1999), Fulton's puzzles (Knutson-Tao 2003); Fulton Young Tableaux §5 surveys the rule. The Vershik-Kerov-Logan-Shepp limit shape and Baik-Deift-Johansson's connection to Tracy-Widom are in Baik-Deift-Suidan Combinatorics and Random Matrix Theory (AMS GSM 172, 2016). Crystal-theoretic proofs of these statements are in Bump-Schilling Crystal Bases: Representations and Combinatorics (World Scientific, 2017).

Connections [Master]

• 07.05.01 (symmetric group representation) is the parent unit; Young diagrams are its combinatorial backbone, and each irreducible $V^{\lambda }$ is built from a tableau of shape $\lambda$. 07.05.03 (Specht module) gives the modular construction of $V^{\lambda }$ via polytabloids — explicit basis vectors built from tableaux. 07.03.01 (highest weight representation) connects via Schur-Weyl: the Schur module $S^{\lambda }V$ is the irreducible polynomial representation of ${\mathrm{GL}}_d$ with highest weight $\lambda$ (interpreted as a dominant weight). 07.04.01 (Cartan-Weyl classification) places this within the larger Lie-theoretic framework. The Schur polynomial $s_{\lambda }$ is the character of $S^{\lambda }V$, and the ring of symmetric polynomials thus captures the entire polynomial-representation theory of $\mathrm{GL}$. Through Schubert calculus, Young tableaux also enter the cohomology of Grassmannians 04.07.01 and flag varieties; through the Kazhdan-Lusztig theory, into perverse sheaves on flag varieties; through crystal bases, into the affine and quantum settings.

Historical & philosophical context [Master]

Alfred Young (1873-1940) was an English mathematician with an unusual career: educated at Cambridge (Trinity College, Wrangler 1895, Smith's Prize 1897), he took holy orders in 1908 and served as rector of Birdbrook in Essex from 1910 until his death thirty years later. Throughout his parish work, Young pursued mathematics as a sustained sideline, eventually publishing nine papers titled On Quantitative Substitutional Analysis in Proceedings of the London Mathematical Society over thirty-four years: 1900, 1902, 1928, 1929, 1930, 1931, 1932, 1933, and 1934. The series is one of the most remarkable sustained mathematical efforts of the twentieth century — a complete combinatorial theory of symmetric-group representations developed alongside daily clerical duties.

The first paper introduced what are now called Young diagrams (called "frames" by Young) as visual representatives of integer partitions. The second paper introduced Young tableaux (then called "tableaux") as fillings of those frames. Young's deepest contribution is the Young symmetriser $c_{\lambda }\in \mathbb{C}[S_n]$ — a combination of row-symmetrisation and column-antisymmetrisation operators that projects onto the irreducible representation $V^{\lambda }$. The third through ninth papers extended the theory to character calculations, modular phenomena, and applications to the general linear group. Young's prose was idiosyncratic and his constructions were often presented without full proofs of irreducibility, but the overall edifice was correct and complete; later authors (von Neumann, Specht, Robinson, James) filled in the technical details.

Frobenius, working independently in Berlin, gave the character formula for $S_n$ in his 1900 Über die Charaktere der symmetrischen Gruppe in the Sitzungsberichte der Königlich Preussischen Akademie. The two pictures — Frobenius's analytical character formula and Young's combinatorial symmetriser construction — meet in the middle: each computes the same characters of the same irreducibles, indexed by the same partitions. Hermann Weyl's 1939 The Classical Groups unified the two perspectives and connected them to the highest-weight theory of ${\mathrm{GL}}_n$.

The combinatorics of Young's diagrams has continued to grow. Robinson (1938) introduced the row insertion algorithm now called the Robinson-Schensted correspondence after Schensted's 1961 rediscovery and its bijective interpretation; Knuth (1970) generalised it to the RSK correspondence handling matrices with non-negative integer entries. Frame, Robinson, and Thrall (1954) discovered the hook length formula for $f^{\lambda }$. Schützenberger (1963 onwards) developed jeu de taquin and the theory of plactic monoids. Macdonald (1979) systematised the entire algebra of symmetric functions in his monograph Symmetric Functions and Hall Polynomials. Kashiwara (1990s) introduced crystal bases and revealed the tableau combinatorics as the limit of quantum-group representation theory at $q=0$. The Young-Frobenius construction is now one of the most thoroughly developed and widely applied pieces of mathematics, with a primary reference (Macdonald) running to several hundred pages and active research continuing across combinatorics, geometry, integrable systems, and probability theory. ^{[Alfred Young 1900-1933 I-IX]}

Bibliography [Master]

• Young, On Quantitative Substitutional Analysis I-IX, Proceedings of the London Mathematical Society (1900, 1902, 1928, 1929, 1930, 1931, 1932, 1933, 1934).
• Frame-Robinson-Thrall, "The hook graphs of the symmetric group," Canadian Journal of Mathematics (1954).
• Robinson, "On the representations of the symmetric group," American Journal of Mathematics (1938).
• Schensted, "Longest increasing and decreasing subsequences," Canadian Journal of Mathematics (1961).
• Knuth, "Permutations, matrices, and generalised Young tableaux," Pacific Journal of Mathematics (1970).
• Greene-Nijenhuis-Wilf, "A probabilistic proof of a formula for the number of Young tableaux of a given shape," Advances in Mathematics (1979).
• Fulton, Young Tableaux: With Applications to Representation Theory and Geometry (LMS Student Texts 35, Cambridge 1997).
• Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions (Springer GTM 203, 2nd ed. 2001).
• Stanley, Enumerative Combinatorics Vol. II (Cambridge 1999), Ch. 7 (symmetric functions and RSK).
• Macdonald, Symmetric Functions and Hall Polynomials (2nd ed., Oxford 1995).
• Knutson-Tao, "The honeycomb model of ${\mathrm{GL}}_n(\mathbb{C})$ tensor products I: proof of the saturation conjecture," Journal of the AMS (1999).
• Bump-Schilling, Crystal Bases: Representations and Combinatorics (World Scientific, 2017).
• Baik-Deift-Suidan, Combinatorics and Random Matrix Theory (AMS GSM 172, 2016).