= Solution
A <near Young tableau> is a filling of a <Young diagram> by distinct entries from a totally ordered alphabet, increasing along rows and down columns; the entries need not be $1,\ldots,n$. For <row insertion> of $x$, scan the first row for its leftmost entry larger than $x$. If one exists, replace it by $x$ and insert the displaced entry into the next row by the same rule. Otherwise append $x$ to the row and stop. Continue until a new outer-corner box is appended.
The <Robinson–Schensted correspondence> inserts the letters $x_1,\ldots,x_n$ of a permutation successively to form $P$. Whenever the $k$th insertion creates a new cell, put $k$ in that cell of a second tableau $Q$. <Row insertion> preserves increasing rows and columns, so $P$ is standard; the sequence of growing diagrams makes $Q$ standard, with the same shape. To reverse the construction, remove the box carrying the largest label in $Q$, and reverse the bumping in $P$: in each row above, exchange the carried entry with the rightmost smaller entry, continuing up to the first row. The final expelled entry is the last letter of the permutation. Repeating recovers the whole permutation, establishing the <bijection> with pairs of <standard Young tableaux> of a common shape.
For the bumping inequality, each displaced entry is the first entry strictly larger than the incoming one. Thus every step replaces a larger entry with a smaller entry and carries that larger value downwards. Consequently \b[the bumped values strictly increase]:
$$
\boxed{x<x'<x''<x'''<\cdots}.
$$
Back to article page
