Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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.

share|improve this answer
    
This is the number of standard Young tableaux. –  Yuval Filmus Mar 9 '11 at 2:15
1  
@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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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