Enumeration of Standard Young Tableau of bounded height - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T17:53:13Z http://mathoverflow.net/feeds/question/47070 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/47070/enumeration-of-standard-young-tableau-of-bounded-height Enumeration of Standard Young Tableau of bounded height Vasu vineet 2010-11-23T08:15:32Z 2010-11-23T08:15:32Z <p>First for some notation $$l(\lambda) = \text{ number of parts in a partition } \lambda \vdash n$$</p> <p>$$f_{\lambda} = \text{number of standard Young tableau of shape } \lambda\vdash n$$</p> <p>The number $f_{\lambda}$ is given by the hook length formula and might not acquire a "nice form". Given an integer $k$ consider the problem of computing $$\tau_{k}(n) = \displaystyle\sum_{\lambda\vdash n \text{, } l(\lambda)\leq k}f_{\lambda}$$</p> <p>Contrary to expectation, relatively neat closed forms are known for $\tau_{2}(n)$, $\tau_{3}(n)$ and $\tau_{4}(n)$. Gessel <a href="http://people.brandeis.edu/~gessel/homepage/papers/dfin.pdf" rel="nofollow">link text</a> proved the following $$\tau_{2}(n) = \binom{n}{\lfloor \frac{n}{2} \rfloor}$$ $$\tau_{3}(n) = M_{n}$$ $$\tau_{4}(n) = C_{\lfloor \frac{n+1}{2} \rfloor}C_{\lceil \frac{n+1}{2} \rceil}$$ where $M_{n}$ denotes the n'th Motzkin number <a href="http://oeis.org/A001006" rel="nofollow">link text</a> and $C_{n}$ denotes the n'th Catalan number <a href="http://oeis.org/A000108" rel="nofollow">link text</a></p> <p>(Here both sequences are indexed starting 0)</p> <p>(Aside: Proving the first two identities bijectively is a cute exercise in my opinion.)</p> <p>As a by-product of my research I obtained the following identity $$\displaystyle\sum_{\lambda\vdash n, l(\lambda)=5,\lambda_{5}=1}f_{\lambda} = \displaystyle\frac {\lfloor \frac{k+1}{2} \rfloor (\lceil \frac{k+1}{2} \rceil +1)}{k+1}C_{\lfloor \frac{k+1}{2} \rfloor}C_{\lceil \frac{k+1}{2} \rceil} - C_{\lfloor \frac{k}{2} \rfloor +1}C_{\lceil \frac{k}{2} \rceil +1}+M_{k}$$ where the sum on the left runs over all partitions $\lambda$ with length exactly 5 and minimum part $\lambda_{5}$ being 1. Admittedly this is very specific but my question is what is known about sums of the above sort </p> <p>a) where the minimum part is fixed and so is the length of the partition ?</p> <p>b) where $l(\lambda) \leq k$ and the k'th part $\lambda_{k} \leq i$ for a fixed non-negative integer $i$?</p> <p>Gessel, I believe, used some really clever symmetric function manipulation to obtain the identities mentioned earlier. I'd appreciate if somebody has seen this stuff elsewhere ( i.e. reference other than Gessel / Gouyou-Beauchamps) and directs me. Thanks!</p>