Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 103 / 4

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.

For $k=1$, the product is empty and equals the identity, the only $1$-cycle in $S_1$. Suppose the cycle-sum identity for Young–Jucys–Murphy elements holds at $k-1$:Multiplication by $X_k={\sum }_{a<k}(ak)$ gives terms $\sigma (ak)$. With permutation products acting right to left, this inserts $k$ immediately after $a$ in the cycle of $\sigma$: the arrows become $a\mapsto k\mapsto \sigma (a)$, with the other arrows unchanged.

Conversely, in any $k$-cycle there is a unique predecessor $a$ of $k$. Delete $k$ and join that predecessor to the successor of $k$; this uniquely recovers $\sigma$ and the factor $(ak)$. Hence every $k$-cycle occurs exactly once, and no other permutation occurs. Induction provesThus ${\xi }_k$ is a conjugacy-class sum in $\mathbb{C}{S}_k$, although it need not be central in $\mathbb{C}{S}_n$ when $k<n$.

Let $T$ be a standard Young tableau of shape $\lambda ⊢n$, and let $\mu$ be the shape formed by its entries $1,\dots ,k$. Since Young–Jucys–Murphy elements act by contents, the eigenvalue of ${\xi }_k$ on its Gelfand–Tsetlin basis vector isIf $\mu$ is not a hook partition, it contains $(2,2)$, whose content is zero, so this product is zero. If $\mu =(a+1,1^b)$ with $a+b+1=k$, its nonzero contents are $1,\dots ,a$ and $-1,\dots ,-b$. Their product is independent of the order of the labels. Therefore the eigenvalue isThe empty product at $k=1$ gives $1$. When $k=n$, $\mu =\lambda$, giving exactly the hook-versus-nonhook distinction suggested by the hint. For $k<n$, it is the intermediate shape $\mu$, rather than the final shape $\lambda$, that controls the answer.

There are $(k-1)!$ $k$-cycles in $S_k$, and each has the same character value of a representation on $S^{\lambda }$. Taking traces in the cycle-sum identity for Young–Jucys–Murphy elements yieldsOnly tableaux whose first $k$ entries form a hook partition contribute.

Write such a shape as ${\mu }_b=(k-b,1^b)$, for $0\le b\le k-1$. There are $f_{{\mu }_b}=\left(\genfrac{}{}{0ex}{}{k-1}{b}\right)$ ways to fill it: choose which $b$ of the labels $2,\dots ,k$ go below the first box. There are $f^{\lambda /{\mu }_b}$ ways to fill the remaining skew diagram with the labels $k+1,\dots ,n$, in standard order. The eigenvalue from part (ii) is $(-1{)}^b(k-b-1)!b!$, so the factoris $1$. Therefore the general character value isHere $f^{\lambda /\mu }$ counts standard skew Young tableaux, and is zero when $\mu$ is not contained in $\lambda$. In particular, for a full $n$-cycle,For $k=1$, the general formula gives $f^{\lambda /(1)}=f_{\lambda }$, the character value at the identity, as it should.

Set $L_i={\lambda }_i+k-i$, for $1\le i\le k$. These are distinct nonnegative integers with $L_1>\cdots >L_k$. Using the falling factorial, the matrix entry can be writtenWhen $k-j>L_i$, the falling factorial vanishes, agreeing with the stipulated convention for a negative factorial argument.

The column polynomials $(X{)}_{k-1},(X{)}_{k-2},\dots ,(X{)}_0$ are monic of successive descending degrees. Subtracting lower-degree combinations of columns turns them into $X^{k-1},X^{k-2},\dots ,1$ without changing the determinant. The Vandermonde determinant therefore givesThe positive sign comes from reversing the usual increasing-degree Vandermonde columns at the same time as writing the differences as $L_i-L_j$.

We now match this denominator with the hook-length formula. The hook lengths in row $i$ are preciselyTo verify the claim, the first hook in the row has length $L_i$. As the column index passes from $j$ to $j+1$, its hook length drops by $1$ plus the number of lower rows ending at column $j$. The skipped lengths are exactly $L_i-L_r$ for those rows: if ${\lambda }_r=j$, then $L_i-L_r={\lambda }_i-j+r-i$. At the right-hand end, lower rows having the same length as row $i$ account for the missing smallest lengths by the same formula. This describes all omitted values, and the remaining count is $L_i-(k-i)={\lambda }_i$.

ConsequentlyCombining the two identities with the hook-length formula proves the determinantal dimension formula