1
$\begingroup$

Consider the Young's lattice. What is the number of paths starting from the origin (0) to a specific Young diagram?

For instance, the Young diagram corresponding to the integer partition 1+1+1 has 1 path leading to it, 2+1 has 2 paths leading to it and 2+2 has 2 paths leading to it.

Is there a generating function to get this combinatorics?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

These paths are the same thing as standard Young tableaux, which are enumerated by the famous Hook Length Formula.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks! Are the some well known polynomials that capture these hook lengths? Something along the lines of: $x_1^2 +x_2$ for N=2, $x_1^3+2x_1x_2+x_3$ for N=3.. and so on? If yes, is there a generating function for this? $\endgroup$
    – TheTwistedSector
    Commented Sep 25, 2021 at 14:11
  • 1
    $\begingroup$ @TheTwistedSector: are you asking for a formula for the number of SYTs of shape $\lambda=(\lambda_1,\lambda_2,\ldots)$ in terms of the $\lambda_1,\lambda_2,\ldots$? There is such a formula due to Frobenius/Young, which significantly predates the Hook Length Formula, using a determinant. See Theorem 2.1.2 of users.math.msu.edu/users/bsagan/papers/old/uyt.pdf. $\endgroup$
    – Sam Hopkins
    Commented Sep 25, 2021 at 14:56
  • 1
    $\begingroup$ Let $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_\ell)$ be a partition of $n$. If instead of $x_{\lambda_1}\cdots x_{\lambda_\ell}$ you use the Schur function $s_\lambda$ (in the variables $y_1,y_2,\dots$), and if $f^\lambda$ denotes the number of paths from $(0)$ to $\lambda$, then $\sum_\lambda f^\lambda s_\lambda= s_1^n = (y_1+y_2+\cdots)^n$, where $\lambda$ ranges over all partitions of $n$. One place where this theory is developed is Chapter 7 of Enumerative Combinatorics, vol. 2. $\endgroup$
    – Richard Stanley
    Commented Sep 25, 2021 at 14:58
  • $\begingroup$ Thanks everyone! @SamHopkins Yes, I was asking for that formula in terms of the $\lambda_i$'s. However, why is it that the number of SYTs = the number of paths? Is there some intuitive way to understand it? $\endgroup$
    – TheTwistedSector
    Commented Sep 25, 2021 at 15:46
  • 1
    $\begingroup$ @TheTwistedSector: yes, the numbers in the boxes tell you the order they are added when going from $\varnothing$ to $\lambda$ one box at a time. This is implicit in Christian's answer. $\endgroup$
    – Sam Hopkins
    Commented Sep 25, 2021 at 16:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .