Insert the successive letters of a permutation by row insertion to obtain an insertion tableau , recording the insertion times in the new boxes of . This is a bijection between permutations and pairs of standard Young tableaux of a common shape. Reverse insertion removes the box marked by the latest recording time. The first row of has length equal to the longest increasing subsequence.
List each pair with multiplicity , sorted first by and then by . Apply row insertion to the lower letters , and record the upper letters in the new cells. The row insertion comparison is strictly greater than the carried entry. The result is a pair of Semistandard Young tableaux of the same shape. Reverse insertion removes the rightmost cell containing the largest recording entry, then replaces the rightmost strictly smaller entry in each preceding row. It reconstructs the ordered list, proving the bijection. The insertion and recording contents are respectively the column sums and row sums of .
If a standard Young tableau of shape has second-row entry , then its self-pair under RSK corresponds to the adjacent transposition . Inserting the word first appends increasing entries to the first row. At time , inserting bumps into the unique second-row cell. Every later entry appends to the first row. Thus the insertion tableau is the stated tableau, and the recording tableau has its second-row label as well. This proves the correspondence directly, including , without invoking a separate theorem about involutions.
The RSK insertion shape is the integer partition giving the row lengths of the insertion tableau in the Robinson-Schensted-Knuth correspondence. The recording tableau has the same shape. For ordinary row insertion, a new entry replaces the first strictly larger entry in a row, bumping it to the next row; if none exists it is appended.
Inserting the word gives rows and , so the shape is . Under this convention, the first row length is the length of a longest weakly increasing subsequence, while the first column length is the length of a longest strictly decreasing subsequence. The shape summarizes ordered structure even when the original word is much longer.
At one matrix entry , let be the shapes of the northwest, northeast, southwest and southeast matrix prefixes under the RSK correspondence. The displayed row-length recurrence expresses merged insertion paths: the new entry supplies the first-row carry, and the overlap of the two incoming row extensions beyond the northwest shape is bumped into the next row. Zero boundary shapes determine the whole diagram. Transposing the matrix exchanges , leaving the rule invariant.
For a symmetric nonnegative integer matrix, the two neighboring prefix shapes along the diagonal are equal. In the RSK growth-diagram local rule, set and take alternating sums of row lengths. The two occurrences of the alternating sum of cancel, leaving . Induction along the diagonal proves the formula. Each column contributes one to this alternating sum exactly when its length is odd.
For a finite - matrix, list its occupied pairs by increasing top entry and decreasing bottom entry within a top-entry tie. Perform ordinary semistandard row insertion on the bottom entries and record top entries in the new cells. The result is a bijection with same-shape tableaux for which and are Semistandard Young tableaux. The types of and are respectively the column-sum and row-sum vectors of the matrix.

Articles by others on the same topic (1)

The Robinson–Schensted correspondence is a combinatorial bijection between permutations and pairs of standard Young tableaux of the same shape. It was introduced independently by John H. Robinson and Ferdinand Schensted in the mid-20th century. The correspondence is an important tool in representation theory, algebraic combinatorics, and the study of symmetric functions. ### Key Components: 1. **Permutations**: A permutation of a set is a rearrangement of its elements.