[proofplan] We prove that one Schensted row insertion preserves the invariant of being a strictly row- and column-increasing tableau of Young diagram shape. The row condition follows from the leftmost-larger rule. The column condition follows from the monotonicity of the bumping path: the columns in which entries are bumped move weakly to the left as the insertion descends. Iterating this one-letter result from the empty tableau gives the desired tableau with exactly the inserted letters, and order-preserving relabelling preserves all inequalities. [/proofplan] [step:Prove the local row insertion invariant] Let $T$ be a tableau of Young diagram shape with strictly increasing rows and columns, and let $a\in A$ be a letter not appearing in $T$. We prove that inserting $a$ into $T$ by Schensted row insertion again produces a tableau of Young diagram shape with strictly increasing rows and columns. During the insertion, define $x_r\in A$ to be the letter inserted into row $r$. If $x_r$ is appended to row $r$, the algorithm stops. If $x_r$ bumps an entry from row $r$, let $j_r$ be the column in which the bump occurs and let $x_{r+1}$ be the bumped entry. Thus, before the replacement in row $r$, the entry in position $(r,j_r)$ is $x_{r+1}$, and after the replacement it is $x_r$. The row condition is preserved in row $r$. If $x_r$ is appended, then every old entry in that row is less than $x_r$, because no old entry is strictly larger than $x_r$. If $x_r$ replaces the leftmost entry strictly larger than it in column $j_r$, then every entry to the left is less than $x_r$, while the old entry in column $j_r$ is $x_{r+1}>x_r$ and was less than every old entry to its right. Hence the modified row remains strictly increasing. [guided] We isolate one insertion because the full theorem is an induction over the letters of the word. Let $T$ be a tableau of Young diagram shape whose rows and columns are strictly increasing, and let $a\in A$ be a new letter. The insertion process moves down through the rows. We write $x_r$ for the letter currently being inserted into row $r$. There are two possibilities in row $r$. If no entry of row $r$ is strictly larger than $x_r$, then the algorithm appends $x_r$ at the end of that row and stops. Since every old entry in that row is then less than $x_r$, the row remains strictly increasing. Otherwise, let $j_r$ be the first column whose entry is strictly larger than $x_r$. The algorithm replaces the old entry in position $(r,j_r)$ by $x_r$ and bumps the old entry, which we call $x_{r+1}$, into the next row. Because $j_r$ is the first column with entry greater than $x_r$, every entry to the left of column $j_r$ is less than $x_r$. Because the old row was strictly increasing, the old entry $x_{r+1}$ in column $j_r$ was less than every entry to its right. Since $x_r<x_{r+1}$, the new entry $x_r$ is also less than every entry to its right. Therefore the row remains strictly increasing after the replacement. [/guided] [/step] [step:Show the bumping path moves weakly left] Assume that $x_r$ bumps $x_{r+1}$ from column $j_r$ in row $r$, and that the algorithm continues to row $r+1$. Let $j_{r+1}$ be the column in which $x_{r+1}$ is either inserted by bumping or appended. If row $r+1$ has a box in column $j_r$, then the old column inequality gives \begin{align*} T(r,j_r)=x_{r+1}<T(r+1,j_r). \end{align*} Thus the leftmost entry in row $r+1$ strictly larger than $x_{r+1}$ occurs in some column $j_{r+1}\leq j_r$. If row $r+1$ has no box in column $j_r$, then its length is at most $j_r-1$, so appending or bumping occurs in a column $j_{r+1}\leq j_r$. Hence the bumping columns satisfy \begin{align*} j_{r+1}\leq j_r \end{align*} whenever both sides are defined. [/step] [step:Use path monotonicity to preserve all column inequalities] Only entries on the bumping path can affect column inequalities. Consider a replacement in row $r$ and column $j_r$, where $x_r$ replaces $x_{r+1}$. For the entry below, if position $(r+1,j_r)$ exists before the replacement, then the old column inequality gives \begin{align*} x_{r+1}<T(r+1,j_r). \end{align*} Since $x_r<x_{r+1}$, we get \begin{align*} x_r<T(r+1,j_r). \end{align*} Thus the lower column inequality remains strict. For the entry above, suppose $r>1$ and position $(r-1,j_r)$ exists after the preceding replacement. Since the bumping path moves weakly left, $j_r\leq j_{r-1}$. In row $r-1$, the letter $x_r$ was bumped from column $j_{r-1}$, so after the preceding replacement the entries of row $r-1$ are still strictly increasing and the entry in column $j_{r-1}$ is $x_{r-1}<x_r$. Therefore, if $j_r<j_{r-1}$, the entry in position $(r-1,j_r)$ is less than the entry in position $(r-1,j_{r-1})$, hence is less than $x_r$. If $j_r=j_{r-1}$, the entry above is $x_{r-1}<x_r$. Thus the upper column inequality remains strict. When the algorithm stops by appending $x_s$ to row $s$, the Young diagram property ensures that any box above the new box exists only if its column is at most the previous bumping column. The same argument using weak-left path monotonicity and the strict row increase in row $s-1$ shows that the entry above the new box is less than $x_s$. Therefore all column inequalities are preserved. [/step] [step:Add exactly one box and preserve Young diagram shape] At every nonterminal bumping step, the algorithm replaces one existing entry by another, so the number of boxes does not change. The only new box is created at the terminal step, when the current letter is appended at the end of some row. The weak-left movement of the bumping path implies that this appended box occurs in a row position compatible with the Young diagram shape: no lower row is longer than the row above it after the append. All other row lengths are unchanged. Hence one row length increases by exactly one, the resulting shape is still a Young diagram, and the number of boxes increases by exactly one. [/step] [step:Iterate the one-letter insertion result] Start with the empty tableau $T_0$. For $0\leq k<m$, let $T_{k+1}$ be obtained from $T_k$ by inserting $w_{k+1}$. The empty tableau has Young diagram shape and has strictly increasing rows and columns. By the local insertion invariant proved above, each $T_k$ has Young diagram shape and strictly increasing rows and columns. At the $k$th insertion, the algorithm only moves existing entries and adds the new letter $w_k$ once. Since the letters $w_1,\dots,w_m$ are pairwise distinct, no equality of entries is introduced. Therefore $T_m$ has exactly $m$ boxes and is filled precisely by the letters $w_1,\dots,w_m$. [/step] [step:Relabel by order to obtain a standard Young tableau] Define the relabelling map \begin{align*} \rho:\{w_1,\dots,w_m\}&\to \{1,\dots,m\} \end{align*} by declaring $\rho(b)=k$ when $b$ is the $k$th smallest letter among $\{w_1,\dots,w_m\}$. The map $\rho$ is strictly order-preserving: for letters $b,c\in\{w_1,\dots,w_m\}$, if $b<c$, then $\rho(b)<\rho(c)$. Applying $\rho$ entrywise to $T_m$ preserves every strict row and column inequality. The resulting tableau has Young diagram shape, contains each of the entries $1,\dots,m$ exactly once, and has strictly increasing rows and columns. Hence it is a standard Young tableau. [/step]