0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – darij grinberg Aug 19 '15 at 18:41
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$ – Traxter Oct 27 '13 at 21:01
  • 1
    $\begingroup$ 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). $\endgroup$ – Henry Oct 27 '13 at 21:07
  • $\begingroup$ 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? $\endgroup$ – Traxter Oct 27 '13 at 21:23
  • $\begingroup$ The applet runs a recursion: the code can be seen at that page $\endgroup$ – Henry Oct 28 '13 at 1:22

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.