7
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is the number of standard Young tableaux. $\endgroup$ Mar 9, 2011 at 2:15
  • 1
    $\begingroup$ @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." $\endgroup$ Mar 9, 2011 at 7:27
  • $\begingroup$ ...except that I've now edited the Wikipedia page so that it says standard tableaux, and has a link to the hook-length formula. $\endgroup$ Mar 9, 2011 at 7:38
2
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.