Skip to content

A Holey Hook Walk

Consider the Ferrer’s diagram for partition $\lambda \vdash N$. We slightly generalize the situation, and we consider Ferrer’s diagrams with some number of boxes deleted. We set $Y_n = Y_n(\lambda)$ to be the set of these deleted diagrams where there are exactly $n$ deletions. The set $Y_0$ consists solely of the Ferrer’s diagram for $\lambda$, and $Y_N$ is the completely deleted (“empty”) diagram. A vector $\boldsymbol \gamma = (\gamma_0, \ldots, \gamma_N)$ is an exhaustion of $\lambda$ if $\gamma_0 = \lambda$, $\gamma_n \in Y_n$ and each $\gamma_n$ is formed from $\gamma_{n-1}$ by deleting a single box. Let us write $\gamma_n \lessdot \gamma_{n-1}$ in this situation.

Given $\gamma \in Y_n$ and $\square \in \lambda$ we define $a_{\gamma}(\square)$ to be the number of (non-deleted) boxes in $\gamma$ in the same row to the right of $\square$, and $\ell_{\gamma}(\square)$ to be the number of (non-deleted) boxes in the same column and below $\square$. Note that $\square$ itself does not contribute to the count in either $a_{\gamma}(\square)$ or $\ell_{\gamma}(\square)$. With parameters $p, q, c$ we define the height of $\square$ in $\lambda$ with respect to $\gamma$ by $H_{\gamma}(p,q,c;\square) = p a_{\gamma}(\square) + q \ell_{\gamma}(\square) + c.$

To $\gamma$ we associate two global functions on $\lambda$, $$F_{\gamma}(p,q,c) = (N-n)! \prod_{\square \in \lambda} \frac{1}{H_{\gamma}(p,q,c; \square)},$$ and $$F^{\circ}_{\gamma}(p,q,c) = (N-n)! c^{N-n} \prod_{\square \in \gamma} \frac{1}{H_{\gamma}(p,q,c; \square)}.$$

Given a box $(u,v) \in \gamma$ we may construct $\gamma’ \in Y_{n-1}$ by deleting $(u,v)$ from $\gamma$. Let’s look at $F_{\gamma’}/F_{\gamma}$ and $F^{\circ}_{\gamma’}/F^{\circ}_{\gamma}$. Define $A_{\gamma’} = \{ a < u : (a, v) \mbox{ is a box in } \gamma \}$ and $B_{\gamma’} = \{ b < v : (u, b) \mbox{is a box in } \gamma\}$. That is $A_{\gamma’}$ indexes the surviving boxes in the anti-hook of $(u,v)$ and $B_{\gamma’}$ indexes the surviving boxes in the anti-hook of $(u, v)$ in both cases, not including $(u,v)$ itself. When we delete $(u,v)$ to produce $\gamma’$, the only terms that change when considering $F_{\gamma}$ are those in the anti-hook of $(u,v)$ and hence, we find $$ \frac{F_{\lambda’}}{F_{\lambda}} = \frac{1}{(N-n)} \prod_{a \in A_{\gamma’}} \frac{H_{\gamma}(a,v)}{H_{\gamma’}(a,v)} \times \prod_{b \in B_{\gamma’}} \frac{H_{\gamma}(u,b)}{H_{\gamma’}(u,b)},$$ and $$ \frac{F^{\circ}_{\lambda’}}{F^{\circ}_{\lambda}} = \frac{1}{(N-n)} \prod_{a \in A_{\gamma’}} \frac{H_{\gamma}(a,v)}{H_{\gamma’}(a,v)} \times \prod_{b \in B_{\gamma’}} \frac{H_{\gamma}(u,b)}{H_{\gamma’}(u,b)} \times \frac{c}{H_{\gamma}(u,v)}.$$

Using standard hook walk maneuvers, we see $$\frac{F^{\circ}_{\lambda’}}{F^{\circ}_{\lambda}} = \frac{1}{(N-n)} \sum_{A \subseteq A_{\gamma’}} \sum_{B \subseteq B_{\gamma’}} \prod_{a \in A} \frac{p}{H_{\gamma’}(a,v)} \times \prod_{b \in B} \frac{q}{H_{\gamma’}(u,b)} \times \frac{c}{H_{\gamma}(u,v)}.$$

To explicitly attach probabilities to our holey hook walk on $\gamma$, once the walker is at a box $\square \in \gamma$, with probability $p/H_{\gamma}(\square)$ it steps uniformly to a non-deleted box in its arm (not itself), and with probability $q/H_{\gamma}(\square)$ it steps uniformly to a non-deleted box it its leg (still not itself). With probability $c/H_{\gamma}(\square)$ the walker deletes $\square$ to produce some $\gamma’ \in Y_{n+1}$. If we assume our walker can start at any of the $N – n$ non-deleted boxes in $\gamma$, then $F^{\circ}_{\gamma’}/F^{\circ}_{\gamma}$ is the probability of walking to $(u,v)$ and then deleting it to produce $\gamma’$.

Thus, if we sum over all $\gamma’ \lessdot \gamma$ we find $$\sum_{\gamma’ \lessdot \gamma} \frac{F^{\circ}_{\gamma’}}{F^{\circ}_{\gamma}} = 1.$$ This basically says that with probability one, our walker will delete one of the remaining $(u,v)$ in $\gamma$.

Theorem: $$F_{\gamma}^{\circ} = \sum_{\gamma’ \lessdot \gamma} F_{\gamma’}^{\circ}.$$

When $c = 0$, our hook walker can only walk to corners on the Ferrer’s diagram, and if $p = q$ then we recover the classic hook walk.

Note that if we construct an exhaustion $\boldsymbol \gamma$ of $\lambda$ by repeatedly walking to a square until the walk terminates and deleting this square, then we get a filling of $\lambda$ by $\{1, 2, \ldots, N\}$.

Leave a Reply

Your email address will not be published. Required fields are marked *