so my question is:

What is the generating function for the number of Young diagrams of a given semiperimeter?

My approach: knowing that there exists a diagram with zero boxes, $$a_0=1$$$$a_1=2$$ $$...$$ so I got the sequence $$A(q)=2^0,2^1,...,2^q$$ and that corresponds to a sequence of semiperimeters, $$1,2,...,n$$ which gives a straightforward polynomial $$f(q) = 1/(1-2q).$$ Is it right? Thank you.

  • $\begingroup$ What Young diagram has perimeter 2? $\endgroup$ – Alien May 14 '20 at 4:20
  • $\begingroup$ None, but if it has semiperimeter $2$ the diagram can be written with two boxes. $\endgroup$ – Luís Felipe May 14 '20 at 4:34
  • $\begingroup$ Then why do you have $$a_1=2$$? $\endgroup$ – Alien May 14 '20 at 4:35
  • $\begingroup$ Because the young diagram whose semiperimeter is $1$, is represented by $2$ boxes and so on. $\endgroup$ – Luís Felipe May 14 '20 at 4:46
  • $\begingroup$ You can't have a young diagram whose semiperimeter is 1. I challenge you to draw one. I'm assuming by semiperimeter you mean half the perimeter. $\endgroup$ – Alien May 14 '20 at 4:55

I believe you meant to write $A(q)=1,0,1,2,4,8,16,...$ and this is true. We will demonstrate on Young Tableaus with semiperimeter 5 and the same process can be repeated for all $n\geq 2$.

First, we notice that Young Tableaus have the property that all horizontal edges not on top can be projected down onto some line without overlap. The same can be said for the vertical edges, so the total perimeter is the Rectangular hull of the Young Tableau. For Tableaus with semiperimeter 5, these Rectangular hulls can be 1x4, 2x3, 3x2, or 4x1. Now notice a unique Young Tableau is determined through the order of Horizontal or Vertical edges from left to right, bottom to top.

The first edge must be horizontal from left to right and the last edge must be vertical for a non-degenerate Tableau, so the number of possible Tableaus in the nxm Rectangular hull is the number of ways to order n-1 vertical edges and m-1 horizontal edges or ${m + n - 2 \choose m-1}$ It is now easy to see that the number of Young Tableaus of semiperimeter 5 becomes the combinatorial sum ${3 \choose 0}+{3\choose 1}+{3\choose 2}+{3\choose 3}=2^3$ since $m+n=5$.

The same process can be generalized for all $n\geq 2$ with $a_n=2^{n-2}$, and the special cases $a_0=1$ and $a_1=0$.

This gives the generating function $A(x)=\frac{(1-x)^2}{1-2x}$ or $\frac{1-2x+x^2}{1-2x}$ or $1+\frac{x^2}{1-2x}$

  • $\begingroup$ You're completely right, thank you so much for the explanation as well. $\endgroup$ – Luís Felipe May 14 '20 at 7:07

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.