The Hook Length Formula and Rsk Correspondence — Examples

The conjugate partition is ${\lambda }^{\mathrm{\prime }}=(3,2,1)$: each column of $[\lambda ]$ has heights $3,2,1$.

Evaluating $h(i,j)={\lambda }_i-j+{\lambda }_j^{\mathrm{\prime }}-i+1$: $h(1,1)=5$, $h(1,2)=1+2=3$, $h(1,3)=0+1=1$, $h(2,1)=1+3-2+1=3$, $h(2,2)=0+2-2+1=1$, $h(3,1)=0+3-3+1=1$; the hook product is $5\cdot 3\cdot 1\cdot 3\cdot 1\cdot 1=45$.

The removable nodes are $(1,3),(2,2),(3,1)$: each of these is the last box of its row and of its column, while $(1,1),(1,2),(2,1)$ each have a box to the right (and $(1,2),(2,1)$ a box below); indeed $(1,2)$ has $(1,3)$ to its right and $(2,2)$ below, $(2,1)$ has $(2,2)$ to its right, and $(1,1)$ has $(1,2)$ to its right.

By [F2], $f^{(3,2,1)}=6!\mathrm{/}45=720\mathrm{/}45=16$.

The three removals are $(2,2,1)$, $(3,1,1)$ and $(3,2)$, of sizes $5$; by [F2] applied in size $5$ and the hook computations: $P(2,2,1)=4\cdot 2\cdot 3\cdot 1\cdot 1=24$ so $f^{(2,2,1)}=120\mathrm{/}24=5$; $P(3,1,1)=5\cdot 2\cdot 1\cdot 2\cdot 1=20$ so $f^{(3,1,1)}=120\mathrm{/}20=6$; $P(3,2)=4\cdot 3\cdot 1\cdot 2\cdot 1=24$ so $f^{(3,2)}=120\mathrm{/}24=5$.

By [F3] the removal recursion predicts $f^{(3,2,1)}=f^{(2,2,1)}+f^{(3,1,1)}+f^{(3,2)}=5+6+5=16$, which agrees with step 3.1.

(One row.) For $\lambda =(n)$ one has ${\lambda }_j^{\mathrm{\prime }}=1$ for $1\le j\le n$, so $h(1,j)=n-j+1-1+1=n-j+1$, the hooks are $n,n-1,\dots ,1$, the product is $n!$, and [F2] gives $f^{(n)}=n!\mathrm{/}n!=1$; this includes $n=1$ with the single hook $h(1,1)=1$.

(One column.) For $\lambda =(1^n)$ one has ${\lambda }_1^{\mathrm{\prime }}=n$ and ${\lambda }_j^{\mathrm{\prime }}=0$ for $j\ge 2$, so $h(i,1)=1-1+n-i+1=n-i+1$ for $1\le i\le n$ and there are no other boxes; the hooks are again $n,n-1,\dots ,1$, the product is $n!$, and [F2] gives $f^{(1^n)}=1$.

(Hook shape, $n\ge 3$.) For $\lambda =(n-1,1)$ the conjugate is ${\lambda }^{\mathrm{\prime }}=(2,1,\dots ,1)$ with ${\lambda }_1^{\mathrm{\prime }}=2$ and ${\lambda }_j^{\mathrm{\prime }}=1$ for $2\le j\le n-1$: $h(1,1)=(n-1)-1+2-1+1=n$; for $2\le j\le n-1$, $h(1,j)=(n-1)-j+1-1+1=n-j$, giving the values $n-2,n-3,\dots ,1$; and $h(2,1)=1-1+2-2+1=1$.

(Hook shape, product and count.) The product of the hooks of step 1.3 is $n\cdot (n-2)!\cdot 1=n(n-2)!$ (the factors $n-2,\dots ,1$ contribute $(n-2)!$); hence [F2] gives $f^{(n-1,1)}=n!\mathrm{/}(n(n-2)!)=(n-1)!\mathrm{/}(n-2)!=n-1$.

(The case $n=2$.) Here $(n-1,1)=(1,1)=(1^2)$ is the one-column shape of step 1.2: the formula of step 2.1 reads $n(n-2)!=2\cdot 0!=2$, the hook product is indeed $2$, and $f^{(1,1)}=1=n-1$; the intermediate range $2\le j\le n-1$ is empty and contributes the empty product $1$.

(Endpoint $n=1$.) The shape $(n-1,1)=(0,1)$ is not a partition, so the hook-shape family begins at $n=2$; for $n=1$ the only partitions are $(1)=(1^1)$, covered by steps 1.1 and 1.2 with $f^{(1)}=1$.

(Insertion steps.) Inserting $6$ into the empty tableau gives $P_1=[6]$. Inserting $4$ replaces $6$ in row $1$ and appends the displaced $6$ in the empty row $2$, giving $P_2$. Inserting $1$ replaces $4$ in row $1$, carries $4$ into row $2$ where it replaces $6$, and appends that displaced $6$ in the empty row $3$, giving $P_3$. These are the displayed columns.

(Steps $4$ and $5$.) Inserting $2$ into $P_3$, whose first row is $[1]$ and second row $[4]$, appends $2$ at the end of the first row, giving $P_4$; inserting $5$ into $P_4$ appends it at the end of the first row as $5>2$, giving $P_5$; the new boxes are $(1,2)$ at step $4$ and $(1,3)$ at step $5$.

(Step $6$.) Inserting $3$ into $P_5$, whose first row is $[1,2,5]$ and second row $[4]$: the leftmost entry exceeding $3$ is $5$ at position $3$, so $3$ replaces it and $5$ is carried to the second row, where it is larger than $4$ and is appended; hence $P_6=\begin{array}{lll}1& 2& 3\\ 4& 5& \\ 6& & \end{array}$, with new box $(2,2)$.

(Recording tableaux.) At each step $k$ the label $k$ is written in the new box of that step, which is $(1,1),(2,1),(3,1),(1,2),(1,3),(2,2)$ for $k=1,\dots ,6$; these boxes are exactly those filled in the displayed $Q_1,\dots ,Q_6$, and by [L2] each $Q_k$ is standard of the shape of $P_k$.

(First deletion.) The box of the label $6$ in $Q_6$ is $(2,2)$, the bottom-right corner; reverse deletion starts there with the carried letter $+\mathrm{\infty }$, takes in row $2$ the entry $5$ (the largest entry smaller than $+\mathrm{\infty }$), empties $(2,2)$ and carries $5$; in row $1$ the largest entry smaller than $5$ is $3$ at position $3$, which is overwritten by $5$ and expelled. The result is $P_5$, and the expelled letter $3$ is $w_6$.

(Remaining deletions.) Repeating step 5.1 for the labels $5,4,3,2,1$: deleting the box $(1,3)$ of label $5$ expels $5$ and restores $P_4$; deleting the box $(1,2)$ of label $4$ expels $2$ and restores $P_3$; deleting the box $(3,1)$ of label $3$ expels $1$ and restores $P_2$; deleting the box $(2,1)$ of label $2$ expels $4$ and restores $P_1$; deleting the box $(1,1)$ of label $1$ expels $6$ and leaves $\mathrm{\varnothing }$. Each deletion reverses the corresponding insertion by [L3], and the recorded labels are the boxes listed in the statement.

(Conclusion.) The expelled letters in the order $3,5,2,1,4,6$ are $w_6,w_5,w_4,w_3,w_2,w_1$, i.e. $w$ read backwards; both tableaux are restored to the empty tableau, so the run illustrates the inverse procedure of the Robinson-Schensted correspondence.

($w=(2,1,4,3)$.) Inserting $2,1$ gives the first column $(2)$, then $(1,2)$ after $1$ displaces $2$; inserting $4$ appends it at the end of the first row, giving $(1,4;2)$; inserting $3$ replaces $4$ in the first row and appends $4$ in the second row, giving $P=(1,3;2,4)$. The added boxes in order are $(1,1),(2,1),(1,2),(2,2)$, so $Q$ carries $1,2,3,4$ in those boxes, i.e. $Q=(1,3;2,4)=P$.

($w=(3,2,1)$.) Inserting $3,2,1$ successively replaces the first row entry each time and appends downwards, giving the single column $P=(1;2;3)$; the added boxes are $(1,1),(2,1),(3,1)$, so $Q=(1;2;3)=P$.

(Consistency with the criterion.) Both words are involutions: $(2,1,4,3)=(12)(34)$ and $(3,2,1)=(13)$, and in both cases step 1.1 or step 1.2 found $P=Q$, as [L1] requires; the shapes $(2,2)$ and $(1,1,1)$ are different, so $P=Q$ does not force a single shape.

(Not only single rows.) The identity $123$ has RSK pair $P=Q=(1,2,3)$ of one-row shape $(3)$, while the involution $w=(2,1,4,3)$ has $P=Q$ of shape $(2,2)$ by step 1.1 and the involution $(3,2,1)$ has $P=Q$ of shape $(1,1,1)$ by step 1.2. These non-row examples show that $P=Q$ is not equivalent to $P$ being a single row.

($n=3$ count.) By [F1], ${\sum }_{\lambda ⊢3}{f}^{\lambda }=f^{(3)}+f^{(2,1)}+f^{(1,1,1)}=1+2+1=4$; the four involutions of $\{1,2,3\}$ are the identity $123$, the transpositions $(12)=213$, $(13)=321$ and $(23)=132$, also four in number, matching the bijection of [L1] in size $3$.

($n=0$ pair.) The empty word inserts no letters, so $P(\mathrm{\varnothing })=\mathrm{\varnothing }$; no box is ever added, so the recording tableau is $\mathrm{\varnothing }$ as well; hence the unique element of $X_0$ corresponds under [L1] to the pair $(\mathrm{\varnothing },\mathrm{\varnothing })$ of standard tableaux of the common shape $\mathrm{\varnothing }⊢0$.

($n=1$ pair.) The set $X_1$ has the single word $(1)$; inserting $1$ into the empty tableau appends it in the only box, so $P=[1]$, and the recording tableau carries $1$ in that box, so $Q=[1]$; hence $X_1$ corresponds to the single pair $([1],[1])$ of standard tableaux of shape $(1)$.

($n=0$ hook formula.) $\lambda =\mathrm{\varnothing }$ has no boxes, so its hook product is the empty product $P(\mathrm{\varnothing })=1$, and [L3] gives $f^{\mathrm{\varnothing }}=0!\mathrm{/}1=1$, the number of standard $\mathrm{\varnothing }$-tableaux (the empty tableau alone), in agreement with the single pair of step 1.1.

($n=1$ hook formula.) For $\lambda =(1)$ the unique hook length is $h(1,1)=1-1+1-1+1=1$, so $P((1))=1$ and [L3] gives $f^{(1)}=1!\mathrm{/}1=1$, in agreement with the single pair of step 1.2.

($n=0$ removal recursion.) The empty partition has no removable node, so $\mathrm{Rem}(\mathrm{\varnothing })=\mathrm{\varnothing }$ and the recursion of [L4] is not asserted at $n=0$; the convention $f^{\mathrm{\varnothing }}=1$ of [L3] is consistent with the count of one empty tableau.

($n=1$ removal recursion.) $\mathrm{Rem}((1))=\{(1,1)\}$ and $(1)-(1,1)=\mathrm{\varnothing }$, so the recursion of [L4] reads $f^{(1)}=f^{\mathrm{\varnothing }}=1$, which matches steps 1.2 and 2.2.