Robinson–Schensted correspondence ($\pi ⟷(P,Q)$)

Insert the successive letters of a permutation by row insertion to obtain an insertion tableau $P$, recording the insertion times in the new boxes of $Q$. 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 $P$ has length equal to the longest increasing subsequence.

List each pair $(i,j)$ with multiplicity $a_{ij}$, sorted first by $i$ and then by $j$. Apply row insertion to the lower letters $j$, and record the upper letters $i$ 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 $A$.

At one matrix entry $a$, let $\rho ,\mu ,\nu ,\lambda$ 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 $\mu ,\nu$, 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 $\mu =\nu$ and take alternating sums of row lengths. The two occurrences of the alternating sum of $\mu$ cancel, leaving $o(\lambda )=o(\rho )+a_{ii}$. Induction along the diagonal proves the formula. Each column contributes one to this alternating sum exactly when its length is odd.

For a finite $0$-$1$ 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 $T,U$ for which $T$ and $U^t$ are Semistandard Young tableaux. The types of $T$ and $U$ are respectively the column-sum and row-sum vectors of the matrix.