 RSK insertion shape

The RSK insertion shape is the integer partition giving the row lengths of the insertion tableau $P$ 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 $312$ gives rows $(1,2)$ and $(3)$, so the shape is $(2,1)$. 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.