Tags: #theorem

Statement

Let $\lambda =({\lambda }_1,\dots ,)$ be the Schensted shape of $w$ some permutation. Then,

1. For all $i$, ${\lambda }_1+\cdots +{\lambda }_i$ is equal to the max size of a union of $i$ increasing subsequences in $w$
2. For all $i$, ${\lambda }_1^{\prime }+\cdots +{\lambda }_i^{\prime }$ is equal to the max size of a union of $i$ decreasing subsequences in $w$ - where ${\lambda }_k^{\prime }$ are the entries of the conjugate partition ${\lambda }^{\prime }$ of $\lambda$

Proved in 1979.

Example

Let $w=3,5,2,4,7,1,6$. Then,

• ${\lambda }_1=3$; 3, 5, 6
• ${\lambda }_1+{\lambda }_2=6$ ; 3, 5, 6 and 2, 4, 7
• ${\lambda }_1+{\lambda }_2+{\lambda }_3=7$ ; 3, 5, 6 and 2, 4, 7 and 1
• ${\lambda }_1^{\prime }=3$ ; 5, 4, 1
• ${\lambda }_1^{\prime }+{\lambda }_2^{\prime }=5$ ; 5, 4, 1 and 7, 6
• ${\lambda }_1^{\prime }+{\lambda }_2^{\prime }+{\lambda }_3^{\prime }=7$ ; 5, 4, 1 and 7, 6 and 3, 2

Proof