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.$$

  • $\begingroup$ this is really amazing. Is conjecture 3.3 still open? $\endgroup$ May 7, 2017 at 1:50
  • 2
    $\begingroup$ FYI, the corresponding sequence 1, 12, 95, 624, 3682, 20264, 106203, ... is oeis.org/A038836 (currently with a slightly different formula and no combinatorial interpretation). $\endgroup$ May 7, 2017 at 5:09
  • $\begingroup$ @BrianHopkins: Thanks, Brian. I noticed too. $\endgroup$ May 7, 2017 at 5:25
  • $\begingroup$ I can't check right now, but maybe findstat.org/StatisticsDatabase/St000185 or findstat.org/StatisticsDatabase/St000566 can be summed. $\endgroup$ May 7, 2017 at 7:49
  • 2
    $\begingroup$ @johnmangual: Conjecture 3.3 is still open to the best of my knowledge. $\endgroup$ May 7, 2017 at 14:44

2 Answers 2


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.

  • $\begingroup$ Richard Stanley: I've posted an update to give a recurrence for the RHS of the quantity on the RHS of my question. $\endgroup$ May 14, 2017 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.