The Schensted theorem on longest increasing and decreasing subsequences

(Nonempty basic subsequences.) For each $j\in \{1,\dots ,{\lambda }_1\}$ the final first row of $P(w)=P_N$ has an entry in position $j$, which was placed there at some step, and that step's letter lies in $S_j$; hence $S_j\mathrm{\ne }\mathrm{\varnothing }$. For $j>{\lambda }_1$ no step can place a letter in position $j$, because positions of the first row never exceed ${\lambda }_1$ at the end; hence $S_j=\mathrm{\varnothing }$. So the nonempty basic subsequences are exactly $S_1,\dots ,S_{{\lambda }_1}$.

(Decreasing property and predecessor property.) Each $S_j$ is strictly decreasing in the order of insertion, and each element $x$ of $S_j$ with $j\ge 2$ has an earlier inserted element $y\in S_{j-1}$ with $y<x$; these are the two assertions of the basic subsequence lemma.

(Upper bound for increasing subsequences.) Let $w_{k_1}<\cdots <w_{k_r}$ with $k_1<\cdots <k_r$ be an increasing subsequence. The letters of $w$ are partitioned by the sets $S_j$ (step 1.1), and within a fixed $S_j$ the letters occur in insertion order with strictly decreasing values (step 1.2); an increasing subsequence meets $S_j$ in at most one letter, since two letters of $S_j$ occur in the order of their positions in $w$ and their values decrease. Hence $r\le \mathrm{\#}\{j:S_j\mathrm{\ne }\mathrm{\varnothing }\}={\lambda }_1$, so the longest increasing length is at most ${\lambda }_1$.

(Lower bound for increasing subsequences.) If $N\ge 1$ set ${\lambda }_1\ge 1$ and choose any element $x_{{\lambda }_1}\in S_{{\lambda }_1}$, which exists by step 1.1; recursively for $j={\lambda }_1,\dots ,2$ apply the predecessor property of step 1.2 to $x_j$ to choose $x_{j-1}\in S_{j-1}$ inserted earlier than $x_j$ with $x_{j-1}<x_j$. Reading the letters $x_1,\dots ,x_{{\lambda }_1}$ in the order of the word $w$: by construction the insertion times strictly increase from $x_1$ to $x_{{\lambda }_1}$, so the positions in $w$ strictly increase, and the values strictly increase; hence they form an increasing subsequence of $w$ of length ${\lambda }_1$.

(Increasing case.) For $N\ge 1$ steps 2.1 and 2.2 give that the longest increasing subsequence length equals ${\lambda }_1$; for $N=0$ there is no first row, ${\lambda }_1=0$, and the empty word has no nonempty subsequence, so the longest increasing length is $0={\lambda }_1$.

(Decreasing case.) An increasing subsequence $w_{i_1}^r<\cdots <w_{i_r}^r$ of the reversed word, with $i_1<\cdots <i_r$, corresponds to the index sequence $N+1-i_r<\cdots <N+1-i_1$ in $w$ with $w_{N+1-i_r}>\cdots >w_{N+1-i_1}$, a decreasing subsequence of the same length; the correspondence is a bijection on subsequences, so the longest decreasing length of $w$ equals the longest increasing length of $w^r$, which by step 3.1 is the number of columns of $P(w^r)$.

(Number of rows.) By [L3] the number of columns of $P(w^r)$ equals the number of rows of $P(w)$, namely ${\lambda }_1^{\mathrm{\prime }}$; combining with step 4.1, the longest decreasing subsequence length equals ${\lambda }_1^{\mathrm{\prime }}$. Together with step 3.1 this is the theorem; for $N=0$ both lengths and both ${\lambda }_1,{\lambda }_1^{\mathrm{\prime }}$ are $0$.