# A Question on the Young Lattice and Young Tableaux

Let:

• $\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?

• @YACP OK thank you for the edit. I just didn't know how to list it compactly – 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.
• 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. – Marc van Leeuwen Apr 15 '13 at 16:37