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.ps> or


<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


--
<http://www.itp.uni-hannover.de/~dragon/>


Superstition brings bad luck.



Semi-Standard Young Diagrams and Families
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.


