Young-graph paths correspond to standard tableaux

[construct] Let $\mathrm{\varnothing }={\lambda }^{(0)}\to {\lambda }^{(1)}\to \cdots \to {\lambda }^{(n)}=\lambda$ be a path from $\mathrm{\varnothing }$ to $\lambda$; by [F1] each step $k$ adds one node $y_k$ to $[{\lambda }^{(k-1)}]$ to produce $[{\lambda }^{(k)}]$, and $\mathrm{\mid }{\lambda }^{(k)}\mathrm{\mid }=k$. Define $t:[\lambda ]\to \{1,\dots ,n\}$ by $t(x):=k$ where $x$ is the node added at step $k$. The nodes $y_1,\dots ,y_n$ are pairwise distinct and their union is $[\lambda ]$, because each $y_k$ is the unique element of $[{\lambda }^{(k)}]\setminus [{\lambda }^{(k-1)}]$ and $[\lambda ]={\bigcup }_k[{\lambda }^{(k)}]$; hence $t$ is a well-defined bijection, that is, a $\lambda$-tableau.

[construct] Conversely, let $t$ be a standard $\lambda$-tableau. If $n=0$ take the path of length $0$ at $\mathrm{\varnothing }$; otherwise set ${\lambda }^{(n)}:=\lambda$ and $t_n:=t$, and for $k=n,n-1,\dots ,1$ let $t_{k-1}$ be the standard tableau of size $k-1$ obtained from $t_k$ by deleting the box containing $k$, which by [F5] is removable and leaves a standard tableau; let ${\lambda }^{(k-1)}$ be its shape, a partition of $k-1$ by [F4]. Then $[{\lambda }^{(k-1)}]\subseteq [{\lambda }^{(k)}]$ with exactly one node removed, that node being removable in ${\lambda }^{(k)}$ and addable in ${\lambda }^{(k-1)}$, so ${\lambda }^{(k-1)}\to {\lambda }^{(k)}$ is an edge of the Young graph and we obtain a path from $\mathrm{\varnothing }$ to $\lambda$.

The tableau $t$ of step 1.1 is standard. Let $(i,j),(i,j+1)\in [\lambda ]$. Both lie in $[{\lambda }^{(m)}]$ for $m:=t(i,j+1)$, because $t(i,j+1)=m$ means $(i,j+1)\in [{\lambda }^{(m)}]$, and then $(i,j)\in [{\lambda }^{(m)}]$ by left-closure of the Young diagram $[{\lambda }^{(m)}]$, [F3]. Since $[{\lambda }^{(m)}]={\bigcup }_{l\le m}[{\lambda }^{(l)}]$ and the $y_l$ are distinct, $(i,j)$ was added at a step $t(i,j)\le m=t(i,j+1)$; the two boxes are distinct, so $t(i,j)\mathrm{\ne }t(i,j+1)$ and therefore $t(i,j)<t(i,j+1)$. The same argument with up-closure in place of left-closure gives $t(i,j)<t(i+1,j)$ whenever both boxes lie in $[\lambda ]$. Hence $t$ is standard.

The path of step 1.2 has the property that ${\lambda }^{(k)}$ is the diagram of the boxes of $t$ carrying labels $\le k$. Indeed ${\lambda }^{(n)}=[\lambda ]$ is all boxes, and at each step the box deleted from ${\lambda }^{(k)}$ is the box of the largest label $k$, which is present in ${\lambda }^{(k)}$ because deleting the boxes of the largest labels $n,n-1,\dots ,k+1$ leaves all boxes with labels $\le k$; hence by downward induction on $k$ the diagram $[{\lambda }^{(k)}]$ is exactly the set of boxes with labels in $\{1,\dots ,k\}$ and has size $k$.

The two constructions are mutually inverse. Starting from a path and forming $t$ by step 1.1, step 2.2 shows that the path recovered from $t$ by the deletion procedure of step 1.2 has ${\lambda }^{(k)}$ equal to the set of boxes with labels $\le k$, which is exactly the diagram of the $k$-th vertex of the original path by definition of $t$; so the recovered path is the original one. Starting from a standard $t$ and forming the path by step 1.2, the tableau produced from that path by step 1.1 assigns to each box the index $k$ at which it was deleted in the construction of step 1.2, which is its label; so the recovered tableau is $t$. Hence the two assignments are inverse bijections between the set of paths from $\mathrm{\varnothing }$ to $\lambda$ and the set of standard $\lambda$-tableaux.

Applying the bijection of step 3.1, the number of paths from $\mathrm{\varnothing }$ to $\lambda$ equals the number of standard $\lambda$-tableaux, which is $f^{\lambda }$ by [F2]. For $\lambda =\mathrm{\varnothing }$ both sets consist of one element: the unique path of length $0$ by [F1] and the empty tableau by [F2]. This proves the corollary.