TAOCP 5.1.4 Exercise 2
For each entry $a_i$ of the permutation, let $t_i$ be the class defined in the text.
Section 5.1.4: Tableaux and Involutions
Exercise 2. [**] [M20] (C. Schensted.) Let $P$ be the tableau corresponding to the permutation $a_1 a_2 \dots a_n$. Prove that the number of columns in $P$ is the longest length $c$ of an increasing subsequence $a_{i_1} < a_{i_2} < \dots < a_{i_c}$, where $i_1 < i_2 < \dots < i_c$; the number of rows in $P$ is the longest length $r$ of a decreasing subsequence $a_{j_1} > a_{j_2} > \dots > a_{j_r}$, where $j_1 < j_2 < \dots < j_r$.
Verified: yes
Solve time: 14m53s
For each entry $a_i$ of the permutation, let $t_i$ be the class defined in the text. By (19), the entries in column $t$ of $P$ are precisely the values $p_{i1},p_{i2},\ldots,p_{im}$ belonging to class $t$, and by (18) they satisfy $$ p_{i1}>p_{i2}>\cdots>p_{im}, $$ while their indices satisfy $$ i_1<i_2<\cdots<i_m. $$ Hence every column of $P$ determines a decreasing subsequence of the permutation, whose length is the number of entries in that column. Consequently the length $r$ of the first column, which is the number of rows of $P$, is not greater than the maximum length of a decreasing subsequence.
Conversely, let $$ a_{j_1}>a_{j_2}>\cdots>a_{j_s}, \qquad j_1<j_2<\cdots<j_s, $$ be any decreasing subsequence. When $a_{j_\nu}$ is inserted, every earlier term $a_{j_\mu}$ with $\mu<\nu$ is larger; therefore $a_{j_\nu}$ cannot belong to a class smaller than $\nu$. Thus $$ t_{j_\nu}\ge \nu. $$ Since class number equals column number, the tableau must contain a column numbered at least $s$. Therefore $s\le r$. Combining this with the previous paragraph shows that $r$ is exactly the maximum length of a decreasing subsequence.
Apply this result to the inverse permutation. By Theorem B, passage to the inverse permutation interchanges $P$ and $Q$, hence transposes the shape. A decreasing subsequence of the inverse permutation corresponds to an increasing subsequence of the original permutation. Therefore the maximum length $c$ of an increasing subsequence of $a_1,a_2,\ldots,a_n$ equals the number of rows of the tableau corresponding to the inverse permutation, which is the number of columns of $P$. Thus the number of columns of $P$ is the longest length of an increasing subsequence, and the number of rows of $P$ is the longest length of a decreasing subsequence. This completes the proof.
∎