The Robinson–Schensted–Knuth correspondence

To insert a value a into a row, replace the first entry greater than a by a and insert the displaced value into the next row. If no entry is greater, append a at the row end and stop. Eventually a new box is created. The bumping inequalities ensure that the resulting diagram is a partition and that column strictness survives. This preservation is a theorem about the specified rule; replacing greater than by greater than or equal changes the convention and the resulting subsequence statistic.

For a permutation w of 1 through n, start with empty P and Q. Insert successive values of w into P; put the insertion time i into Q at the single new box. Both tableaux are standard, since each input value and each time appears once. They have the same shape but generally different entries. The common first-row length is the length of a longest increasing subsequence of w, and the first-column length is the length of a longest decreasing subsequence, with subsequences preserving positions rather than requiring consecutive entries.

For permutations, locate the largest recording label n, remove its corner box from Q, and remove the value in the corresponding box of P. Move that value upward by reverse insertion: in the row above, replace the rightmost entry smaller than the carried value and carry the displaced entry upward. The value exiting the first row is the final input. Repeating reconstructs the word backward. The corner location and strict inequality make this a deterministic inverse rather than a guess at a possible original order.

For a matrix of nonnegative integers, form a multiset of pairs (i,j) containing each pair with its matrix multiplicity. Sort pairs by increasing i and, among equal i, increasing j. Insert the lower entries j and record upper entries i in new boxes. Now both P and Q are semistandard, and their contents are the matrix column sums and row sums respectively. The total number of boxes is the sum of all entries. This lexicographic ordering is part of ordinary RSK, not an optional preprocessing choice.

For a general word, recording the distinct insertion times still gives a standard Q, whereas P may contain repeats. Under this row convention, its first row measures the longest weakly increasing subsequence; its first column measures the longest strictly decreasing subsequence. The distinction disappears for permutations but matters immediately for a constant word: every equal value appends, producing one row. A claim about strictly increasing subsequences for arbitrary repeated words would therefore be false.

The shape forgets information even though the full pair is reversible. Two words can have the same insertion tableau but different recording tableaux, and many pairs can share a shape. In algebraic combinatorics this controlled loss is useful: grouping matrices or permutations by shape factors an enumeration into two tableau counts. It is also a warning when interpreting an algorithmic output: a shape is a statistic, P is a richer invariant, and the ordered pair carries the information needed for inversion.