Tags: #definition

Schensted shape

For some permutation $w$, its Schensted shape is the partition $\lambda =\lambda (w)$ that is the shape of the Young tableau(x) that you get from applying the Schensted insertion algorithm.

Properties

• ${\lambda }_1$ is equal to the max length of increasing subsequences of $w$ proof here
• ${\lambda }_1^{\prime }$ (ie. the first column) is equal to the max length of decreasing subsequences in $w$
• If applying the Schensted algorithm to $w$ yields $(P,Q)$, then applying it to $w^{-1}$ yields $(Q,P)$. In particular, this means that $\lambda (w)=\lambda (w^{-1})$.
• As corollaries:
  • $n!=\sum _{\lambda ⊢n}(f_{\lambda }{)}^2$ where $f_{\lambda }$ is the number of standard Young tableaus of size $\lambda$.
    • 
  • the number of 123-avoidant permutations in $S_n$ is equal to the number of pairs $(P,Q)$ of shape $\lambda$ where ${\lambda }_1\le 2$
    • In particular this is equal to the number of standard Young tableaux of shape $(2^n)$
      • We can stack the two pairs by flipping one of them and adding them to the end. We renumber by replacing $i$ with $2n+1-i$ after flipping. This yields a tableaux with shape $(2^n)$
      • 
    • This connects the two proofs that number of 3-permutation-avoiding permutations is catalan and also the number of SYTs of shape (n, n) is catalan since the conjugate partition of $(2^n)$ is $(n,n)$