• $\lambda \vdash n$ be a partition of $n$
  • $f^\lambda$ - number of standard Young Tableaux of shape $\lambda$
  • $\succ$ - be the covering in the Young Lattice (that is, $\mu \succ \lambda$ iff $\mu$ is obtained by adding a single box to $\lambda$)

Then I want to show:

$$\frac{\sum_{\mu \succ \lambda}f^\mu}{f^\lambda}=n+1$$ This is the last step in a proof I've come up with showing the well-known relation

$$\sum_{\lambda \vdash n}(f^\lambda)^2=n!$$

Can someone help verify that the former formula is true, and, if so, perhaps have ideas on how may I show it?

  • $\begingroup$ @YACP OK thank you for the edit. I just didn't know how to list it compactly $\endgroup$ – gone Apr 15 '13 at 17:33

You want to show that $(n+1)f^\lambda=\sum_{\mu\succ \lambda}f^\mu$, in other words that given an element $i\in\{1,2,\ldots,n+1\}$ and a standard tableau of shape $\lambda$ you can build a standard tableau of some shape obtained by adding a single square to the shape, and do so in a bijective (reversible) way. You may renumber the entries of the tableau monotonically so that it contains all numbers of $\{1,2,\ldots,n+1\}\setminus\{i\}$. Then what you are asking for is exactly achieved by Schensted insertion.

This is in fact easy to prove directly, see Lemma 1.3.1. of this paper, which gives the following proof by induction on $n=|\lambda|$. Since $f^{(0)}=f^{(1)}=1$ the starting case $n=0$ is OK. Now assuming $n>0$ one has $$ (n+1)f^\lambda =f^\lambda+n\sum_{\mu\prec\lambda}f^\mu =f^\lambda + \sum_{\mu\prec\lambda}\sum_{\nu\succ\mu}f^\nu $$ by induction (where the first equality harks back to $f^{\lambda} = \sum_{\mu\prec\lambda}f^\mu$, a consequence of the fact that the standard tableaus of shape $\lambda$ are in bijective correspondence with the standard tableaus of all shapes $\mu$ such that $\mu\prec\lambda$; this correspondence is given by cutting off the square containing $n$). In the double summation we distinguish terms $\nu=\lambda$, of which there are $\#\lambda^-$ where $\lambda^-=\{\,\mu\mid\mu\prec\lambda\,\}$, and terms with $\nu\neq\lambda$. The latter $\nu$ are obtained by removing a square and adding a different square to the shape; this can also be done in the opposite order giving first a shape $\kappa\succ\lambda$ and then $\nu\prec\kappa$. Defining $\lambda^+=\{\,\mu\mid\mu\succ\lambda\,\}$ one has $\#\lambda^+=\#\lambda^-+1$, since for every square that we can remove from the shape there is a square that we can add to the shape in the next row, and we can also always add a square to the first row. Now write our expression as $$ (1+\#\lambda^-)f^\lambda +\sum_{\mu\prec\lambda}\sum_{\textstyle{\nu\succ\mu\atop\nu\neq\lambda}} f^\nu =\#\lambda^+f^\lambda +\sum_{\kappa\succ\lambda}\sum_{\textstyle{\nu\prec\kappa\atop\nu\neq\lambda}} f^\nu = \sum_{\kappa\succ\lambda}\sum_{\nu\prec\kappa}f^\nu = \sum_{\kappa\succ\lambda}f^\kappa, $$ where the final equality comes from extending a standard Young tableau of shape $\nu$ to one of shape $\kappa$ by adding the entry $n+1$ in the unique new square. This completes the induction step.

The above proof uses exactly the propreties than make Schensted insertion tick, namely that Young's lattice is a $1$-differential poset. In fact if one translates this proof, which is entirely based on bijections, into a recursively defined procedure for extending Young tableaux, the resulting procedure is equivalent, under the natural identifications, to Schensted insertion. You can do the same for any differential poset, giving rise to "Schensted" insertion procedures for each of them. Also the structure of the proof can be made evident by instead of a recursive procedure turning it into a (Fomin) growth diagram construction of Schensted insertion, or more precisely of the full Robinson-Schensted correspondence. Again this extends to arbitrary differential posets.

  • $\begingroup$ Thank you Marc for this amazing reply. I have not seen the Schensted insertion so I will definitely take a look at it. I have seen Stanley's paper on differential posets, but to be honest I can't quite see what's going on there - what they are. Again, thank you for the response, and I will ponder it $\endgroup$ – gone Apr 15 '13 at 15:18
  • $\begingroup$ But I'm not surprised you mentioned differential posets - the formula I've given is a last-step in an alternative proof I've come up with to attempt to circumvent using differential posets to get the factorial structure! $\endgroup$ – gone Apr 15 '13 at 15:21
  • $\begingroup$ Well, I guess there is no way of getting around the differential poset structure; as I said it is exactly what makes this proof work. But it is a very simple notion: for any $\nu\neq\lambda$ but at the same level as $\lambda$ there are as many ways (and at most one) to get there via down-up as via up-down, while for $\lambda$ itself there is one more way (for a $t$-differential poset $t$ more ways) to get there by up-down than by down-up. $\endgroup$ – Marc van Leeuwen Apr 15 '13 at 16:37

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.