Tags: #theorem

Statement

where $\lambda$ is a partition of $n$, $f_{\lambda }$ is the number of SYTs with shape $\lambda$.

Proof 1 (RSK)

Robinson-Schensted-Knud (RSK) correspondence gives a bijection between all permutations of $S_n$ and pairs of SYTs of $\lambda ⊢n$. The number of items in the latter is exactly the LHS of the above equation, and the former is exactly $n!$.

Proof 2 (Young's lattice)

Note that $f_{\lambda }$ is the number of saturated chains in Young's lattice from $\mathrm{\varnothing }\to \lambda$, and so $(f_{\lambda }{)}^2$ are pairs of paths from $\mathrm{\varnothing }\to \lambda$; equivalently, paths from $\mathrm{\varnothing }\to \mathrm{\varnothing }$ with $n$ ups and $n$ downs (ie. we go up to some $\lambda$ and then we go down, so that gives us two paths from $\mathrm{\varnothing }\to \lambda$).

Let $V_n$ be a vector space over $\mathbb{R}$ with basis $\{v_{\lambda }{\}}_{\lambda ⊢n}$. This is a $p(n)$-dimensional vector space (where $p(n)$ is the partition function). Let $V=V_0\oplus V_1\oplus V_2\oplus \dots$. Define up and down operators on this space as follows:

• $U:V_n\to V_{n+1}$ by mapping $v_{\lambda }\mapsto \sum _{\mu ⋗\lambda }{v}_{\mu }$
• $D:V_{n+1}\to V_n$ by mapping $v_{\lambda }\mapsto \sum _{\mu ⋖\lambda }{v}_{\mu }$

For example, (I use partition notation, but in class we drew the tableaux)

• $U(v_{\mathrm{\varnothing }})=v_{(1)}$
• $UU(v_{\mathrm{\varnothing }})=v_{(2)}+v_{(1,1)}$
• $UUU(v_{\mathrm{\varnothing }})=(v_{(3)}+v_{(2,1)})+(v_{(2,1)}+v_{(1,1,1)}-v_{(3)}+2v_{(2,1)}+v_{(1,1,1)}$
• $DUUU(v_{\mathrm{\varnothing }})=v_{(2)}+2(v_{(2)}+v_{(1,1)})+v_{(1,1)}=3v_{(2)}+3v_{(1,1)}$
• $DDDUUU(v_{\mathrm{\varnothing }})=6v_{\mathrm{\varnothing }}$ note the coefficient of which is $3!$

From this, we claim that $D^n{U}^n(v_{\mathrm{\varnothing }})=n!v_{\mathrm{\varnothing }}$. We shall prove this by first proving the following lemma:

Key lemma: $DU-UD=I$ and $D(v_{\mathrm{\varnothing }})=0$

• The second statement is true from the definitions.
• Note that the LHS of the first statement is the commutator but notably this does not say that it is commutative (the RHS would have to be zero).
• Example: Let $\lambda =(3,1)$. Then, we note that $DU(v_{\lambda })=v_{(4)}+v_{(2,2)}+3v_{(3,1)}$ and $UD(v_{\lambda })=v_{(4)}+v_{(2,2)}+2v_{(3,1)})$. Their difference is indeed $v_{(3,1)}$.
• Proof: Rephrasing this combinatorially, it is saying that if we have $\lambda$ a Young diagram, it satisfies the following two conditions
  • A) the number of ways to get from $\lambda \to \mu$ (for $\lambda \ne \mu$) via an up step then a down step (in Young's lattice) is equal to the number of ways to get from $\lambda \to \mu$ via a down step and then an up step
    • Note that if we can reach $\mu$ from $\lambda$ in this manner, we'd be able to get there by moving a box in $\lambda$ somewhere else to get $\mu$. From here, we see that this is true.
  • B) if there are $a$ items that are covered by $\lambda$, then there are $a+1$ items covering $\lambda$.
    • To get something covering $\lambda$, we can add a box to an outer corner of its Young diagram (open dot)
    • To get something covered by $\lambda$, we may remove a box from an inner corner of its Young diagram (filled in dot)
    • 
    • We note that these boxes are always alternating and that there will be one more outer corner than inner corner

With the key lemma, we may prove this two ways:

2a (induction)

We shall proceed via induction on $n$. The base case is trivial.

Now let us try applying this to $v_{\mathrm{\varnothing }}$. By the second statement in the lemma, the second term here becomes zero. Thus,

2b (derivatives)

Consider the two operators acting on $\mathbb{R}[x]$:

• $x:f\mapsto xf(x)$
• $\frac{d}{dx}:f(x)\mapsto f^{\prime }(x)$

They satisfy the same identities as above:

• $\frac{d}{dx}(xf(x))-x\left(\frac{d}{dx}f\right)=f(x)$
• $\frac{d}{dx}(1)=0$
  So, any identities that these satisfy will hold for $D,U$ as well. We know that

and so we may use this to conclude.