# Hooks in a staircase partition: Part I

This quest has its impetus in a paper by Stanley and Zanello. I became curious about

What is the sum of all hooks lengths of all partitions that fit inside the $n$-th staircase partition?

On the basis of experimental data, I'm prompted to ask:

Question. Let $\lambda=(n,n-1,\dots,1)$ be the staircase partition, $h_{\square}$ the hook-length of a cell $\square$ in the Young diagram of a partition. Then,
$$\sum_{\mu\subset\lambda}\sum_{\square\in\mu}h_{\square}=\frac{(n+4)(2n+3)}6\binom{2n+2}{n+1} - (n+2) 2^{2n+1}.$$ Is this true? If so, any proof?

Update. I'm still hoping for a complete solution for this evaluation; it's not common to get such a nice closed from in general. Part II of this problem has received a fine answer.

Update. To help Stanley's mention of a recurrence, denote the RHS quantity by $w_n:=\frac{(n+4)(2n+3)}6\binom{2n+2}{n+1} - (n+2) 2^{2n+1}$ then we have ("shaloshable") $$n(n-2)w_n-2(4n^2-5n-3)w_{n-1}+8n(2n-1)w_{n-2}=0.$$

The following method should give a proof, but I haven't done the computation. Let $f_n$ denote the desired sum. I use the result of Douglas Zare's answer that $$f_n = \sum_{\mu\subseteq \delta_n} \sum_i \mu_i^2,$$ where $\delta_n=(n,n-1,\dots,1)$. Let $$g_n = \sum_{\mu\subseteq \delta_n} \sum_i \mu_i.$$ By OEIS A029760 we have $$g_n = \frac 12 (n+2)^2C_n-2^{2n+1},$$ where $C_n$ is a Catalan number.

We now break up the sum for $f_n$ into the following parts:

(1) No $\mu_i=n-i+1$. In other words, $\mu\subseteq\delta_{n-1}$, so the contribution from these terms is $f_{n-1}$.

(2) $\mu_1=n$. Below the first row is any partition $\nu\subseteq \delta_{n-1}$, so the contribution from these terms is $f_{n-1}+n^2C_n$ since there are $C_n$ choices for $\nu$.

(3) $\mu_k=n-k+1$ for some $k\geq 2$, and $\mu_j<n-j+1$ for $j<k$. The first $k-2$ rows of $\mu$ consist of a $(k-2)\times(n-k+1)$ rectangle with a partition $\nu\subseteq\delta_{k-2}$ on the right. Rows $k-1$ and $k$ of $\mu$ have length $n-k+1$. The remaining rows ($k+1$ to $n$) consist of a partition $\rho\subseteq \delta_{n-k}$. Each $\nu$ occurs $C_{n-k+1}$ times (the number of choices for $\rho$), and each $\rho$ occurs $C_{k-1}$ times. Hence the contribution to the sum for $f_n$ is $$C_{n-k+1}\sum_{\nu\subseteq\delta_{k-2}}\sum_i (\nu_i+n-k+1)^2+ C_{k-1}\sum_{\rho\in\delta_{n-k}} \sum_i \rho_i^2+2C_{n-k+1}C_{k-1}(n-k+1)^2$$ $$= C_{n-k+1}(f_{k-2}+2(n-k+1)g_{k-2}+C_{k-1}(k-2)(n-k+1)^2)+ C_{k-1}f_{n-k}+2C_{n-k+1}C_{k-1}(n-k+1)^2.$$

Summing over all possibilities gives a recurrence satisfied by $f_n$. It should be routine (i.e., "shaloshable") to check that the conjectured answer satisfies the recurrence. Perhaps there is some inaccuracy in the details above, but I think that the general idea should give a solution.

• Richard Stanley: I've posted an update to give a recurrence for the RHS of the quantity on the RHS of my question. – T. Amdeberhan May 14 '17 at 3:18

I think this is progress.

The hook length of square $S$ is the count of the squares $R$ directly below or to the right of $S$ plus 1. So, in a particular partition, the sum of the hook lengths is the count of the pairs $(S,R)$. It's simpler to count these pairs by $R$. The number of such pairs is the sum over all squares $R=(x,y)$ of $(x+y-1)$ (if you number the rows starting with $1$).

$$\sum_{\mu \subset \lambda} \sum_{(x,y)\in \mu} (x+y-1)$$

Since the staircase is self-conjugate, the sum of $x$ is the same as the sum of $y$, so we can rewrite this as

$$\begin{eqnarray}2\sum_{\mu \subset \lambda} \sum_{(x,y) \in \mu} x - \sum_{\mu \subset \lambda} |\mu| &=& \sum_{\mu \subset \lambda} \sum_i (\mu_i^2+\mu_i) - \sum_{\mu \subset \lambda} |\mu| \newline &=& \sum_{\mu \subset \lambda} \sum_i \mu_i^2\end{eqnarray}$$

where $\mu_i$ is the size of the $i$th part of $\mu$.

Counting partitions $\mu$ inside a staircase $\lambda$ so $\mu_i=j$ can be done with two applications of reflection.