# the number of Young tableaux in general

From the wiki page Catalan number, we know the number of Young tableaux whose diagram is a 2-by-n rectangle given $2n$ distinct numbers is $C_n$. In general, given $m\times n$ distinct numbers, how many Young tableaux whose diagram is a $m\times n$ rectangle are there?

Also, what if these numbers can be repeated?

Many thanks.

-

For the answer to your main question, you need to use the hook-length formula.

OEIS A060854 gives the result $$(mn)! \prod_{i=0}^{n-1} \frac{i!}{(m+i)!} \textrm{ or equivalently } (mn)! \prod_{j=0}^{m-1} \frac{j!}{(n+j)!}$$ and some more information.

-
This is the number of standard Young tableaux. –  Yuval Filmus Mar 9 '11 at 2:15
@Yuval: "Young tableaux" in the question really means "standard Young tableaux". To quote from the Wikipedia page linked to: "$C_n$ is the number of Young tableaux whose diagram is a 2-by-$n$ rectangle. In other words, it is the number ways the numbers $1, 2, \dots, 2n$ can be arranged in a 2-by-$n$ rectangle so that each row and each column is increasing. As such, the formula can be derived as a special case of the hook formula." –  Hans Lundmark Mar 9 '11 at 7:27
...except that I've now edited the Wikipedia page so that it says standard tableaux, and has a link to the hook-length formula. –  Hans Lundmark Mar 9 '11 at 7:38

It not quite clear what you mean by allowing repeated numbers, but what one usually considers in that case is so-called semi-standard Young tableaux, i.e., tableaux which are increasing (strict inequality) down each column, but only nondecreasing (equality allowed) along each row. The number of such arrangements on a given Young diagram, where the numbers $1,2,\dots,N$ are allowed, is counted as follows: define the "content" of box $(i,j)$ in the diagram to be $i-j$. Here's an illustration:

 0  1  2  3  4
-1  0  1  2
-2 -1  0
-3 -2
-4 -3
-5


Hook lengths are defined as for the usual hook-length formula for counting standard Young tableaux:

10  8  5  3  1
8  6  3  1
6  4  1
4  2
3  1
1


To get the answer, take the product over all boxes of (($N$ plus the content of that box) divided by (the hook length for that box)).

(This is a special case of something called Stanley's hook-content formula.)

-