# Number of Young Tableaux of size n with a given number of rows and a distinct number of boxes in each row

I would like to know if there is a formula for the number of Young tableaux of size $n$ with a given number of rows, each row having a distinct number of boxes. I have seen the Hook length formula which gives the number of Young tableaux of shape $\lambda$, but this doesn't seem to help me as I'm not interested in a Young filling.

For example, say I want to know how many Young tableaux of size 6 there are with 2 rows. Then the possible tableaux are those with shape (4,2) and (5,1), hence there are 2 Young Tableaux of size 6 with 2 rows.

Thank you very much in advance for any help.

Edit: I've also seen the recurrence relation $a(n+1)=a(n)+na(n-1)$, with $a(0)=a(1)=1$, where $a(n)$ gives the number of Young tableaux of size $n$.

• For future readers: There seems to be a confusion between Young tableaux and Young diagrams in this post, and the author seems to be interested in Young diagrams. – darij grinberg Aug 19 '15 at 18:41

## 1 Answer

This is equivalent to the number of partitions of $n$ into $k$ distinct positive terms.

This is the same as the number of partitions of $n-\frac{k(k-1)}{2}$ into $k$ positive terms, since you can subtract ${k-1}$ from the largest distinct part, ${k-2}$ from the second largest, and so on down to subtracting $0$ from the smallest distinct part.

So you want the co-efficient of $x^{n-k(k-1)/2}$ in the expansion of $$\frac{x^k}{\displaystyle\prod_{i=1}^{k} (1-x^i)}.$$

You can use recursion, as in in my Java applet at http://www.se16.info/js/partitions.htm : so if you ask for partitions of $6$ into exactly $2$ distinct parts you get a result of $2$; asking for partitions with distinct terms of $6000$ with exactly $20$ parts gives $1470489673468747936729666225918528498$.

• Thank you so much for your answer Henry, that's exactly what I'm looking for, and it's a very lovely formula. Is there a way to put a condition on the maximum length of a row? For example, suppose I want to calculate the number of tableaux of size 7 into 2 rows, where the maximum value for each row is 4. Then we have to exclude the two tableaux of shape (5,2) and (6,1), leaving only one of shape (4,3). – Traxter Oct 27 '13 at 21:01
• You can in the applet: ask for partitions with distinct terms of 7 with exactly 2 parts and each term no more than 4. The answer is 1 (because 7=4+3). – Henry Oct 27 '13 at 21:07
• Wow. I can't thank you enough Henry, you have just made my week. Would you mind giving a brief explanation of the mathematics behind the upper limit? I understand the original formula, is there a similar one that can be written explicitly with the restriction to terms less than or equal to a certain value, or does the applet run an algorithm? – Traxter Oct 27 '13 at 21:23
• The applet runs a recursion: the code can be seen at that page – Henry Oct 28 '13 at 1:22