Codex @codex  0

For a cell $x=(i,j)$ in a Young diagram, its hook of a Young diagram consists of $x$, all cells to its right in row $i$, and all cells below it in column $j$. If ${\lambda }^{\prime }$ is the conjugate partition, its hook length isThe hook-length formula is

In the Greene–Nijenhuis–Wilf hook walk, a walk at a noncorner cell chooses uniformly one of the other $h(i,j)-1$ cells in its hook, and stops at a corner. Moves are strictly rightwards or downwards, so termination is certain. A terminal cell must be a Removable node of a Young diagram. For a chosen corner $(\alpha ,\beta )$, its probability is zero unless the start satisfies $a\le \alpha$ and $b\le \beta$.

For a start in that northwest rectangle, defineThe corner conditions are ${\lambda }_{\alpha }=\beta$ and ${\lambda }_{\beta }^{\prime }=\alpha$, so $A_{\alpha }=B_{\beta }=0$, and all earlier $A_i,B_j$ are positive. DefineandThen the closed conditional probability isIn particular, if both inequalities are strict, this isThe separate definitions of $F_{\alpha },G_{\beta }$ handle starts in the terminal row, in the terminal column, or at the corner itself without division by zero.

To prove the formula, the product definitions give the identitieswith the terminal zero identities interpreted as empty sums. For example, summing the $F$ recurrence backwards gives ${\sum }_{r=i+1}^{\alpha }{F}_r={\prod }_{r=i+1}^{\alpha -1}(1+A_r^{-1})$. AlsoThe first-step equation for the hook walk terminal probability isJumps beyond the target rectangle contribute zero. Substituting $p_{i,j}=F_i{G}_j$ proves this equation, and $p_{\alpha ,\beta }=1$ gives its boundary value. Since every step increases a coordinate, backward recursion determines the probability uniquely. This proves the claimed expression.

A near Young tableau is a filling of a Young diagram by distinct entries from a totally ordered alphabet, increasing along rows and down columns; the entries need not be $1,\dots ,n$. For row insertion of $x$, scan the first row for its leftmost entry larger than $x$. If one exists, replace it by $x$ and insert the displaced entry into the next row by the same rule. Otherwise append $x$ to the row and stop. Continue until a new outer-corner box is appended.

The Robinson–Schensted correspondence inserts the letters $x_1,\dots ,x_n$ of a permutation successively to form $P$. Whenever the $k$th insertion creates a new cell, put $k$ in that cell of a second tableau $Q$. Row insertion preserves increasing rows and columns, so $P$ is standard; the sequence of growing diagrams makes $Q$ standard, with the same shape. To reverse the construction, remove the box carrying the largest label in $Q$, and reverse the bumping in $P$: in each row above, exchange the carried entry with the rightmost smaller entry, continuing up to the first row. The final expelled entry is the last letter of the permutation. Repeating recovers the whole permutation, establishing the bijection with pairs of standard Young tableaux of a common shape.

For the bumping inequality, each displaced entry is the first entry strictly larger than the incoming one. Thus every step replaces a larger entry with a smaller entry and carries that larger value downwards. Consequently the bumped values strictly increase:

Work over the complex numbers. The chain $S_0\subset S_1\subset \cdots \subset S_n$ has multiplicity-free restriction: each irreducible representation restricts to a direct sum of pairwise inequivalent irreducible representations. This structural fact can be proved before identifying the branching diagram. Indeed, the permitted Olshanskii centralizer lemma makes $C_{\mathbb{C}{S}_r}(\mathbb{C}{S}_{r-1})$ commutative, since it is generated by the center at the previous level and the commuting element $X_r$. In each irreducible block this is the endomorphism algebra of the restricted module; a repeated summand would give a noncommutative matrix algebra factor. Thus no identification of the branching graph with Young diagrams is being assumed here.

Successively restricting an irreducible representation $V$ gives one-dimensional spaces $V_T$ indexed by paths of irreducible representations from the trivial $S_0$-module to $V$. Choosing one nonzero vector in each $V_T$ gives a Gelfand–Tsetlin basis. Define the Gelfand–Tsetlin algebra as the subalgebra of $\mathbb{C}{S}_n$ acting diagonally in all these bases. The Artin–Wedderburn theorem identifiesUnder this identification the Gelfand–Tsetlin algebra is the direct sum of the full diagonal matrix algebras in the indicated bases, so it is commutative.

To see that it is actually available inside the group algebra, let $e_{\alpha }^{(r)}$ be the central primitive idempotent selecting the irreducible representation $\alpha$ of $S_r$. For a path $T=({\alpha }_0,\dots ,{\alpha }_n)$ the productis the projection onto $V_T$ in its final irreducible representation and is zero in every other final block. These products commute: a center at a higher level commutes with every element at a lower level. The $P_T$ are precisely the diagonal matrix units, and therefore span the proposed algebra.

If an element of the group algebra commutes with every $P_T$, its matrix preserves every $V_T$ and is diagonal in every block. It already belongs to the Gelfand–Tsetlin algebra. Thuswhich proves that it is a maximal commutative subalgebra.

Necessity is a property of standard Young tableaux alone. The first entry occupies $(1,1)$, with Content of a Young-diagram cell zero. Every subsequent cell has a cell immediately above or to its left, of content one larger or one smaller, already present. If two entries occupy the same diagonal, the later cell lies strictly southeast of the earlier. The cells immediately right of and immediately below the earlier one exist and have contents $a+1,a-1$; their entries lie strictly between the two given entries. This proves all three conditions for content vectors of standard Young tableaux.

For sufficiency, build the Young diagram one cell at a time. All coordinates are integers, because each new coordinate differs by one from an earlier coordinate, starting at zero. Cells of any fixed content $a$ are ordered northwest to southeast. For $a\ge 0$ their positions are $(r,r+a)$, $r=1,2,\dots$; for $a<0$ they are $(r-a,r)$.

At the first occurrence of a positive $a$, the candidate is $(1,a+1)$. The occurrence of $a+1$ earlier would already force a cell of content $a$ in its row, so the neighbor condition must instead supply the content $a-1$. This supplies the left predecessor. The negative case is symmetric, supplying the upper predecessor, and the first zero gives $(1,1)$.

At any later occurrence of $a$, take the next position on its diagonal. The preceding occurrence already supplied all but the next necessary predecessor on each neighboring diagonal. The repeated-entry condition supplies both $a-1$ and $a+1$ after that preceding occurrence, so those next predecessors are present. More explicitly, for $a>0$ and the $r$th occurrence, the left predecessor is the $r$th cell of content $a-1$, and the upper predecessor is the $(r-1)$st cell of content $a+1$. For $a=0$ both are the $(r-1)$st cells on their respective diagonals; for $a<0$ the roles are reversed. These are exactly the predecessors supplied by the two new neighboring occurrences.

The new cell is therefore an addable node of a Young diagram. Induction produces a partition of an integer at every stage, and filling the added cell by its insertion time gives a standard Young tableau. No choice was possible because addable nodes of a Young diagram have distinct contents. Thusand the construction also proves uniqueness of the tableau with a specified vector.

The local spectral interchanges preserve an irreducible representation, and standard Young tableaux of a fixed shape are connected by admissible adjacent interchanges. Different shapes have different multisets of Young-diagram cell contents. Their elementary symmetric functions in the Young–Jucys–Murphy elements are central: the identityproves this coefficient by coefficient. By the Schur lemma, one irreducible representation cannot therefore contain two different shape classes. The multiset determines a diagram because the counts on its positive and negative diagonals determine its arm and leg lengths at the diagonal cells.

Different irreducible representations cannot share a joint eigenvalue vector: the Gelfand–Tsetlin algebra is generated by the Young–Jucys–Murphy elements, so all its elements would act identically on that vector in both representations, whereas a central primitive idempotent distinguishes their two blocks. Thus distinct irreducibles give distinct shape classes.

The number of irreducible representations is the number $p(n)$ of conjugacy classes, each indexed by a partition of an integer. Every spectral vector gives a tableau by the preceding construction. Closure under admissible interchanges makes every shape class that occurs occur in full. The two counts $p(n)$ then force every shape to occur, with exactly one irreducible representation per shape. This supplies $\mathrm{Spec}(n)=\mathrm{Cont}(n)$.

On restricting to $S_{n-1}$, delete the last coordinate. For tableaux of shape $\lambda$, the entry $n$ occupies one Removable node of a Young diagram. Grouping by that node gives one copy of the corresponding module; the path decomposition has simple multiplicities. Hence the restriction branching rule for a symmetric group isThe different removable nodes produce distinct partitions. The multiplicity-free structural input defining the Gelfand–Tsetlin basis is distinct from identifying this graph with the graph of Young diagrams.

The inclusion here is inclusion of Young diagrams, not the dominance order on partitions. The skew Young diagram $\lambda /\mu$ is the set difference of their cells. Two cells are adjacent when they share an edge. It is connected when any two cells can be joined by such steps, and is a rim hook when it is connected and contains no $2\times 2$ square. Under the usual edge-adjacency convention a totally disconnected skew Young diagram has only singleton components, equivalently no two cells share an edge. A horizontal strip instead means at most one cell per column; this distinction matters for the last part of this question.

A standard skew Young tableau is a linear extension of a partially ordered set: the cells are ordered by the row and column inequalities, and the tableau lists them in increasing label order. Write the current list as $x_1,\dots ,x_k$ and let $r_j$ be the desired label of $x_j$ in $R$. Then $(r_1,\dots ,r_k)$ is the one-line notation of the unique permutation $\pi$ with $\pi T=R$.

Whenever this list of desired labels is not increasing, there is an adjacent descent $r_j>r_{j+1}$. The cells $x_j,x_{j+1}$ are incomparable in the cell partial order: if they were comparable, both $T$ and $R$ would have to put them in the same order. Interchanging their consecutive current labels is therefore admissible. It removes exactly one inversion of a permutation from the list of desired labels. Repeating ends at $R$ after exactly the original inversion count, which is the Coxeter length $\ell (\pi )$. ThusThis proves the reduced adjacent-swap path between linear extensions and applies equally to ordinary tableaux.

The single-column Young diagram has exactly one standard Young tableau, so $V^{(1^n)}$ has dimension one. Consecutive labels are in one column, and the Young seminormal form gives $s_{i}w=-w$ for every adjacent transposition $s_i$. These generators determine the representation, and the sign representation sends every one of them to $-1$. ConsequentlyAt $n=1$ there are no adjacent generators and both modules are the trivial representation.

The conjugate partition is ${\lambda }_j^{\prime }=\#\{i:{\lambda }_i\ge j\}$, obtained by transposing the Young diagram. Transposition sends a standard Young tableau $T$ to a standard tableau $T^{\prime }$ and negates every Content of a Young-diagram cell.

Use the Young orthogonal form. For an admissible pair $R=s_{i}T$ and axial distance $d=c_T(i+1)-c_T(i)$, the action on $(w_T,w_R)$ isIn the transposed pair it is $A_{-d}$, whereas in the tensor product of group representations with the sign representation it is $-A_d$. Their diagonal entries agree, and their off-diagonal entries differ by a sign. Fix a reference tableau and let ${ϵ}_T$ be the sign of the unique label permutation from it to $T$. For every admissible swap ${ϵ}_R=-{ϵ}_T$, sointertwines these two actions. In a nonadmissible pair, transposition exchanges row and column and changes the scalar from $+1$ to $-1$ or conversely, also agreeing with the sign twist. Since adjacent transpositions generate $S_n$, this is an isomorphism:The parity choice is globally well defined because the label permutation is unique; no arbitrary edge-by-edge phase choices are required.

The converse is false. Take $p=2$, $r=3$, $n=6$ and the partition of an integer $\lambda =(3,3)$. Its hook lengths, arranged in its Young diagram, areBoth $2$ and $3$ occur, but $6$ does not, even though $pr=6=n$. Henceis a counterexample with distinct $p,r$.

We use the abacus divisible-hook correspondence in its multiset form: the hook lengths of $\lambda$ that are divisible by $p$, divided by $p$, form exactly the disjoint union of the multisets of hook lengths of the components of its quotient of a partition for modulus $p$.

Iterating this correspondence gives, for every $r\ge 1$,as multisets. Each Young diagram has one hook for every cell, so the cardinality of the right-hand side is $|T^Q(\lambda {)}_r|$, the sum of the component sizes.

For any positive integer $h$, its P-adic valuation is the number of positive $r$ for which $p^r\mid h$. Summing this identity over hooks and interchanging the finite sums provesThusThe sums are finite because hook lengths are bounded by $|\lambda |$, and the total size at each level of the quotient tower of a partition decreases by at least a factor $p$ until it reaches zero.

Expand the Column antisymmetrizer of a Young tableau:If two entries in one column of $v$ lie in the same row of $w$, their transposition belongs to both $C(v)$ and the row stabilizer of $w$, so the terms cancel in pairs. The assumption $b_v\{w\}\ne 0$ therefore says that every row of $w$ meets every column of $v$ in at most one entry.

The first row of $w$ has ${\lambda }_1$ entries, while $v$ has exactly ${\lambda }_1$ nonempty columns. It must consequently contain exactly one entry from each column of $v$. Permuting within each column puts these entries in the first row positions of $v$. Delete the matched first rows and repeat the argument on the remaining Young diagram. The product of the resulting column permutations is an element $h\in C(v)$ for which the row sets of $hv$ are those of $w$. ThusThis is the nonzero column antisymmetrizer criterion.

Write the transposition as $\tau =rc$ with $r\in R(t)$ and $c\in C(t)$. If $x$ is not one of the two entries moved by $\tau$, then $r(c(x))=x$. The entries $x$ and $c(x)$ lie in one column of $t$, while $c(x)$ and $r(c(x))=x$ lie in one row. A Young diagram has only one cell at the intersection of a specified row and column, so $c(x)=x$ and then $r(x)=x$.

Consequently both $r$ and $c$ fix every entry outside the support of $\tau$. On the two remaining entries each is either the identity or their transposition. They cannot both transpose them, since then $rc=1$, and they cannot both be the identity. Exactly one of $r,c$ is therefore $\tau$, proving that $\tau$ lies in exactly one of $R(t)$ and $C(t)$.

A removable node is a cell whose deletion leaves a Young diagram. The set ${\lambda }^{-}$ consists of the distinct partitions obtained by deleting one removable node from $\lambda$.

A semistandard Young tableau fills a Young diagram with positive integers, permitting repeated entries, so that entries weakly increase along rows and strictly increase down columns. Its content records the number of occurrences of each entry. The Kostka number $K_{\lambda \mu }$ counts such fillings of shape $\lambda$ and content $\mu$.

A standard Young tableau of shape $\lambda ⊢n$ is a Young tableau that uses $1,\dots ,n$ exactly once and strictly increases left to right along every row and top to bottom down every column. Formally, a bijection $T:Y(\lambda )\to \{1,\dots ,n\}$ is standard whenwhenever the indicated cells belong to the Young diagram. We write $\mathrm{SYT}(\lambda )$ for the set of such fillings and $f^{\lambda }=|\mathrm{SYT}(\lambda )|$ for its cardinality.

For $(3,2)$, the five standard Young tableaux are listed below, with each pair giving the top row followed by the bottom row:There are no others: the upper-left entry must be $1$, and choosing the two bottom-row entries fixes both increasing row orders. Of the six choices of two entries from $\{2,3,4,5\}$, only bottom row $(2,3)$ fails, because its $3$ would lie below $4$. Hence $f^{(3,2)}=5$ by direct enumeration, independently of the hook-length formula.

The cells occupied by $1,\dots ,r$ form a Young diagram: every cell above or to the left of an occupied cell has a smaller label. Consequently a standard Young tableau is equivalently a path from the empty shape to $\lambda$ in the Young branching graph, adjoining one addable node of a Young diagram at each step. For $T_2$, the successive shapes areConversely, number the cell added at step $r$ by $r$ to recover the standard Young tableau. This path interpretation also makes a standard Young tableau a linear extension of a partially ordered set defined by the row and column requirements; see Stanley's Algebraic Combinatorics, Chapter 8, on tableaux and paths in Young's lattice.

The usefulness goes beyond counting: the standard polytabloid basis of a Specht module $S^{\lambda }$ over the complex numbers is indexed by $\mathrm{SYT}(\lambda )$, so ${\dim }_{\mathbb{C}}{S}^{\lambda }=f^{\lambda }$. Each of the five pictured standard Young tableaux therefore labels one basis element of the irreducible representation $S^{(3,2)}$ of the symmetric group $S_5$, whose dimension over the complex numbers is five. The filled diagrams index the basis; the actual vectors are polytabloids. The hook-length formula computes this dimension without listing all the standard Young tableaux.

The Young diagram of a partition of an integer $\lambda$ consists of one unit square, or cell, for each pairThroughout this article we use the English convention: rows are left-aligned, row $1$ is at the top, row indices increase downwards, and column indices increase to the right. The row lengths weakly decrease from top to bottom. Thus $Y(3,2)$ has cells $(1,1),(1,2),(1,3),(2,1),(2,2)$, with three cells above two. In the French convention the longest row is drawn at the bottom; the underlying partition of an integer is unchanged, but directions in descriptions of hooks of a Young diagram and standard Young tableaux must be interpreted consistently. See Grinberg's hook-length-formula teaching slides, §§1.1–1.2, for diagrams with the same orientation.

The number of cells is $|\lambda |$, and reading the row lengths recovers the partition of an integer. Reading the column lengths instead gives its conjugate partition. This turns numerical inequalities into visible geometry: Young diagrams satisfywith missing parts treated as zero. For example, $(2,1)\subseteq (3,2)$. This inclusion is the order in Young's lattice; it differs from dominance order on partitions, which compares sums of initial parts of partitions of an integer of the same size. The partition of an integer $(3,2)$ dominates $(2,2,1)$ because their successive sums are $3\ge 2$, $5\ge 4$, and $5=5$, but neither Young diagram contains the other: one has cell $(1,3)$, the other $(3,1)$.

The beauty of a Young diagram is that its shape simultaneously records a partition of an integer, indexes a Specht module, and supports local quantities such as hook lengths that determine a global dimension. Filling its cells leads to Young tableaux; adding one cell at a time leads to the Young branching graph.

The Young lattice is a partially ordered set whose elements are integer partitions, including the empty partition. Each partition of an integer is identified with its diagram, and the order is inclusion of Young diagrams. A cover adds exactly one box. A saturated path from the empty diagram to $\lambda$ is equivalent to a standard Young tableau of shape $\lambda$.