# Semi-Standard Young Diagrams and Families

In connection with string theory I encountered the following problem:

Given the set M_N of all semi-standard Young tableaux of size N (i.e. all fillings of Ferrers diagrams with natural numbers with weakly increasing rows and strictly increasing columns, the content of which sum to N).

The conjecture, which I cannot prove and for which I know no counterexample states:

M_N is the union of disjoint families, where each family consists of a father diagram and all his daughters, which are obtained from the father diagram by deletion of one box.

The conjecture holds for N<=8

http://www.itp.uni-hannover.de/~dragon/young.pdf

There numbers a,b are attached to the Ferrers diagrams, where a is the number of semi-standard Young Tableaux of size N and b the number of fathers, who remain after the daughters have filled up their families.

Light cone string theory proves that the conjecture holds for all M_N with less than 25 rows, i.e. for N < 325. But string theory provides no counterexample for N >= 325.

Any suggestions, e.g. how to compute the number a(N,lambda) of Young diagrams with size N and shape lambda, would be helpful.

Norbert Dragon

I use standard facts about symmetric functions that can be found, e.g, in Chapter 7 of Enumerative Combinatorics, vol. 2. Let $s_\lambda$ denote a Schur function and $p_1=s_1=x_1+x_2+\cdots$. Then $\frac{\partial s_\lambda}{\partial p_1}=\sum_\mu s_\mu$, where the $\mu$'s are obtained by removing a single box from $\lambda$. Moreover, the coefficient of $q^n$ in $s_\lambda(q,q^2,q^3,\dots)$ is equal to the number of SSYT with entries summing to $n$. Thus if we let $c_n$ be the coefficient of $q^n$ in the symmetric function $f$ defined by $$f+\frac{\partial}{\partial p_1}f = \sum_\lambda s_\lambda\cdot s_\lambda(q,q^2,q^3,\dots),$$ and if $c_n=\sum a_{\mu,n}s_\mu$, then we need $a_{\mu,n}$ copies of the shape $\mu$ in a set of fathers generating all SSYT with entries summing to $n$. Hence we need to show that $a_{\mu,n}\geq 0$. Now $$\sum_\lambda s_\lambda\cdot s_\lambda(q,q^2,q^3,\dots) = \exp \sum_{n\geq 1} \frac{q^n}{1-q^n}p_n.$$ This leads to a simple linear first-order differential equation with solution $$f = (1-q) \sum_\lambda s_\lambda\cdot s_\lambda(q,q^2,q^3,\dots).$$ If $h_u$ denotes the hook length of the square $u$ of $\lambda$, then $$s_\lambda(q,q^2,q^3,\dots) = \frac{q^{b(\lambda)}}{\prod_{u\in \lambda} (1-q^{h_u})},$$ where $b_\lambda=\sum i\lambda_i$. Since there is always a hook length equal to one, the power series $(1-q)s_\lambda(q,q^2,q^3,\dots)$ will be a product of factors of the form $1/(1-q^h)$, $h\geq 1$, so will have nonnegative coefficients as desired. Thus we have not just an existence proof, but a precise generating function for the number of fathers of each shape.