40.03.04 · combinatorics / symmetric-functions-rsk

The Robinson-Schensted-Knuth Correspondence

shipped3 tiersLean: none

Anchor (Master): Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.11-7.14, Appendix 1 (RSK and dual RSK, the Cauchy and dual Cauchy identities as bijective consequences, Greene's theorem, Knuth equivalence and the plactic monoid, the symmetry theorem of Schützenberger); Knuth 1970 *Pacific J. Math.* 34 (the RSK generalisation to matrices); Schensted 1961 *Canad. J. Math.* 13 (longest increasing subsequences); Greene 1974 *J. Combin. Theory A* 14 (the shape via increasing subsequences); Sagan 2001 *The Symmetric Group* 2e Ch. 3; Baik-Deift-Johansson 1999 *J. Amer. Math. Soc.* 12 (the Tracy-Widom limit of the longest increasing subsequence)

Intuition Beginner

Imagine reading off a shuffled list of distinct numbers one at a time, and filing each new number into a growing left-justified array of boxes by a fixed, mechanical rule. The rule is patient: a new number tries to settle at the right end of the top row, but if it is too small to sit there, it shoves out (bumps) the smallest entry that blocks it, and that bumped entry drops to the next row down to repeat the same struggle. Each number you read causes a cascade of bumps that ends by adding exactly one fresh box somewhere. This filing procedure is row insertion, and it is the engine of the whole unit.

Why bother? Because the procedure secretly sorts the chaos of a shuffle into two tidy staircase-shaped tables. One table, $P$ , records where every value finally lands; the other, $Q$ , records the order in which the boxes were born. The remarkable fact is that the original shuffle can be reconstructed perfectly from this pair of tables — nothing is lost. So a shuffle of $n$ numbers and a pair of equally-shaped staircase tables are two names for the same object. This dictionary is the Robinson-Schensted correspondence.

The pay-off is that questions about the shuffle that look hard become easy in the table language. How long is the longest stretch of values that keep increasing, scattered through the shuffle? You do not have to search: it is simply the width of the top row of $P$ . Counting, symmetry, and even the behaviour of a random shuffle all become readable off the shape of the tables. The same filing rule, run on lists with repeats or on grids of counts, gives an even larger dictionary used throughout this chapter.

Visual Beginner

Inserting the permutation $4132$ one value at a time. At each step the new value bumps the leftmost entry strictly larger than it from a row; the bumped entry moves down to the next row and repeats. The recording table $Q$ writes the step number into whichever box is newly created.

step	insert	the table $P$ after the step	new box born
1	$4$	row 1: $4$	top row, position 1
2	$1$	row 1: $1$ ; row 2: $4$	row 2 (the $1$ bumped the $4$ down)
3	$3$	row 1: $13$ ; row 2: $4$	row 1, position 2
4	$2$	row 1: $12$ ; row 2: $34$	row 2, position 2 ( $2$ bumped $3$ down)

The final pair is $P$ with rows $12$ and $34$ , and $Q$ with rows $13$ and $24$ . Both have the same staircase shape (two boxes over two boxes). Notice the entries of $P$ increase along rows and down columns, and so do the entries of $Q$ : each is a standard table, using each number once. The longest increasing run hidden in $4132$ has length $2$ (for instance $13$ or $12$ ), and that is exactly the width of the top row.

Worked example Beginner

Let us run the full filing on the permutation $231$ and read off the two tables, then check the longest-increasing-run fact.

Step 1. Insert $2$ . The top row is empty, so $2$ sits at the start: $P$ has top row $2$ . A box was born at the top-left, so $Q$ has top row $1$ .

Step 2. Insert $3$ . Compare with the top row $2$ . Since $3$ is not smaller than $2$ , it sits at the right end of the top row: $P$ top row becomes $23$ . The new box is the second box of the top row, so $Q$ top row becomes $12$ .

Step 3. Insert $1$ . Compare with the top row $23$ . The value $1$ is smaller than $2$ , so it bumps the $2$ : the top row becomes $13$ , and the bumped $2$ drops to row two. Row two was empty, so $2$ sits there. The new box is the start of row two, so $Q$ gets a $3$ in the new row-two box.

Step 4. Read off. The table $P$ has top row $13$ and second row $2$ . The table $Q$ has top row $12$ and second row $3$ . Both have the same shape: two boxes over one.

Step 5. Check the longest increasing run. In $231$ the longest stretch of values that increase (reading left to right, not necessarily next to each other) is $23$ , length $2$ . The top row of $P$ is $13$ , width $2$ . They match.

What this tells us: the mechanical filing turns a permutation into a matched pair of standard tables, and a feature of the permutation that would take searching — the longest increasing run — is simply the width of the first row. Run in reverse, the same pair rebuilds $231$ , so no information was lost.

Check your understanding Beginner

Exercise (easy, numeric).

Insert the value $5$ into a top row that currently reads $136$ . In which position (counting from the left, starting at $1$ ) does an entry get bumped out of this row?

Hint

The new value goes at the end if it is at least as big as everything; otherwise it replaces the leftmost entry strictly larger than it.

Answer

Position $3$ . Scanning $136$ for the leftmost entry strictly larger than $5$ , the entries $1$ and $3$ are smaller, and $6$ is the first one larger, sitting in position $3$ . So $5$ takes that spot, the row becomes $135$ , and $6$ is bumped down. Feedback-correct: bumping always targets the leftmost entry that exceeds the incoming value, keeping the row sorted. Feedback-wrong: if you answered "no bump, it goes at the end" you treated $5$ as large enough to sit after $6$ , but $5 < 6$ , so the row would no longer increase.

Formal definition Intermediate+

Work with semistandard and standard Young tableaux of 40.03.02; all notation (the shape $λ ⊢ n$ , $SSYT (λ)$ , $SYT (λ)$ , the content, the conjugate $λ^{'}$ , $f^{λ} = ∣ SYT (λ) ∣$ , the Schur function $s_{λ}$ ) is inherited from that unit and recorded in _meta/NOTATION.md. Throughout, tableau means a column-strict, row-weakly-increasing filling.

Definition (row insertion). Let $P$ be a semistandard tableau and $k$ a positive integer. The row insertion $P \leftarrow k$ is computed by: set $i = 1$ and the inserted value $v = k$ . In row $i$ , if $v$ weakly exceeds every entry, append $v$ at the right end and stop; otherwise let the leftmost entry strictly greater than $v$ be at column $j$ , replace it by $v$ (this is a bump), set $v$ to the replaced entry, increment $i$ , and repeat in the next row. The procedure terminates, adding exactly one new cell, and $P \leftarrow k$ is again a semistandard tableau. The cell added is the bump path's terminal cell.

Definition (Robinson-Schensted). For a permutation $σ = σ (1) σ (2) \dots σ (n) \in S_{n}$ , form the insertion tableau $P (σ) = ((\emptyset \leftarrow σ (1)) \leftarrow σ (2)) \leftarrow \dots \leftarrow σ (n)$ and the recording tableau $Q (σ)$ by placing the entry $t$ into the cell created at step $t$ . Then $P (σ), Q (σ) \in SYT (λ)$ for a common shape $λ ⊢ n$ . The Robinson-Schensted map $σ \mapsto (P (σ), Q (σ))$ is a bijection $$ S_n ;\xrightarrow{\ \sim\ }; \bigsqcup_{\lambda \vdash n} \mathrm{SYT}(\lambda) \times \mathrm{SYT}(\lambda). $$

Definition (RSK, the Knuth generalisation). A generalised permutation is a two-line array $(j _{1} j _{2} \dots j _{N} i _{1} i _{2} \dots i _{N})$ whose columns are sorted lexicographically (by top entry, ties broken by bottom entry). Such arrays biject with $N$ -matrices $A = (a_{ij})$ of finite support, $a_{ij} = # {t : (i_{t}, j_{t}) = (i, j)}$ . RSK inserts $j_{1}, \dots, j_{N}$ to build a tableau $P$ and records the top entries $i_{1}, \dots, i_{N}$ in $Q$ at the cells created. It is a bijection $$ {\mathbb{N}\text{-matrices of finite support}} ;\xrightarrow{\ \sim\ }; \bigsqcup_{\lambda} \mathrm{SSYT}(\lambda) \times \mathrm{SSYT}(\lambda), $$ with $content (P) = (column sums of A)$ and $content (Q) = (row sums of A)$ . Restricting to $0/1$ -matrices and using column insertion gives the dual RSK, a bijection between $0/1$ -matrices and pairs $(P, Q)$ with $P \in SSYT (λ)$ , $Q \in SSYT (λ^{'})$ .

Definition (increasing/decreasing subsequences). An increasing subsequence of $σ$ of length $k$ is indices $t_{1} < \dots < t_{k}$ with $σ (t_{1}) < \dots < σ (t_{k})$ ; decreasing reverses the second inequalities. Write $is (σ)$ and $ds (σ)$ for the maximal lengths, and $i_{k} (σ)$ for the maximal size of a union of $k$ increasing subsequences.

Counterexamples to common slips Intermediate+

"Bumping replaces the leftmost entry $\geq v$ ." It replaces the leftmost entry strictly greater than $v$ ( $> v$ , not $\geq v$ ). Using $\geq$ would break column-strictness and is the column-insertion convention instead; mixing the two corrupts the bijection. Equal values append to the right under row insertion, which is exactly why repeated entries are allowed in a row.
"RS works for any sequence, giving two SYT." For a word with repeated letters, $P$ is semistandard (not standard) and the right partner is the RSK recording tableau, also semistandard. Two standard tableaux arise only from genuine permutations (distinct entries). Forcing standardness on a word with repeats loses the content data that RSK is designed to preserve.
"The recording tableau $Q$ tracks the same numbers as $P$ ." $Q$ records creation order (for RS) or the top line of the generalised permutation (for RSK), not the inserted values. Confusing $P$ and $Q$ inverts the roles in the symmetry theorem $σ^{- 1} \mapsto (Q, P)$ .

Key theorem with proof Intermediate+

The signature theorem is that row insertion is invertible step by step, so the Robinson-Schensted map is a bijection enumerating $\sum_{λ} (f^{λ})^{2} = n!$ , and Schensted's theorem reads the longest increasing subsequence off the first row.

Theorem (Robinson-Schensted bijection and Schensted's theorem). The map $σ \mapsto (P (σ), Q (σ))$ is a bijection from $S_{n}$ onto $⨆_{λ ⊢ n} SYT (λ)^{2}$ ; in particular $\sum_{λ ⊢ n} (f^{λ})^{2} = n!$ . The shape $λ = sh (P (σ))$ satisfies $λ_{1} = is (σ)$ , the length of the longest increasing subsequence of $σ$ , and $λ_{1}^{'} = ds (σ)$ , the length of the longest decreasing subsequence. ^{[Stanley §7.11]}

Proof. Two parts: bijectivity by reverse insertion, then Schensted's identification.

(i) Bijectivity. Given $(P, Q) \in SYT (λ)^{2}$ , reconstruct $σ$ . The largest entry $n$ of $Q$ sits in some cell $c$ , necessarily an outer corner of $λ$ (its row and column maximal). The value occupying $c$ in $P$ was the last entry to settle, ending a bump path; reverse the path: starting from $c$ , take the entry $w$ there, move up one row, and find the rightmost entry strictly less than $w$ , swap roles ( $w$ bumps it upward), continuing until reaching row $1$ , where the final ejected value is $σ (n)$ . Deleting cell $c$ from both $P$ and $Q$ yields a smaller pair of equal shape; induction recovers $σ (n - 1), \dots, σ (1)$ . Each reverse step exactly undoes a forward insertion because the forward bump path is monotone (the bumped entries strictly increase as they fall), so the rightmost-smaller search inverts the leftmost-larger search. Forward and reverse are mutually inverse, giving the bijection; counting cardinalities gives $n! = \sum_{λ} (f^{λ})^{2}$ .

(ii) Schensted's theorem. Fix the first row of $P$ . After inserting $σ (1), \dots, σ (t)$ , the entry in cell $(1, j)$ is the smallest possible last value of an increasing subsequence of $σ (1) \dots σ (t)$ of length $j$ . This invariant holds initially and is preserved by insertion: inserting $σ (t + 1) = a$ into position $j$ of row $1$ means $a$ is the new smallest length- $j$ tail, extending the length- $(j - 1)$ subsequence whose tail sat at $(1, j - 1) < a$ . Hence the width $λ_{1}$ of row $1$ equals the maximal length of an increasing subsequence, $is (σ)$ . Applying the same statement to the reversal/complement (insertion of $σ$ read so that increasing becomes decreasing) — equivalently using that $P (σ^{rev})$ is the transpose-compatible tableau — gives $λ_{1}^{'} = ds (σ)$ for the first column. $□$

Bridge. This theorem is the foundational reason RSK is more than an algorithm: the reverse-insertion argument shows the correspondence is a genuine bijection, so it transports any count or symmetry between permutations and tableau pairs. It builds toward the symmetry theorem and Greene's theorem of Advanced results, where transposing the matrix swaps $P$ and $Q$ and unions of increasing subsequences recover the entire shape; and it appears again in 40.03.03, where the same insertion run on generalised permutations is exactly the bijective proof of the Cauchy identity $\sum_{λ} s_{λ} (x) s_{λ} (y) = \prod_{i, j} (1 - x_{i} y_{j})^{- 1}$ . The identity $\sum_{λ} (f^{λ})^{2} = n!$ is dual to the representation-theoretic $\sum_{λ} (dim S^{λ})^{2} = ∣ S_{n} ∣$ of 07.05.03; this is exactly the statement that RS is the combinatorial shadow of the decomposition of the group algebra. Putting these together, Schensted's first-row reading generalises into Greene's theorem, the reverse insertion supplies invertibility, and the content bookkeeping of RSK supplies the symmetric-function identity — three faces of one bumping rule.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Carry out RSK on the $N$ -matrix with generalised permutation $(1 2 1 1 1 2)$ and give the content (row sums) of $Q$ and (column sums) of $P$ .

Hint

Insert the bottom row $121$ into $P$ , recording the top row $112$ in $Q$ . Column sums of $A$ are the content of $P$ ; row sums of $A$ are the content of $Q$ .

Answer

The matrix is $A = (1110)$ (rows/cols indexed $1, 2$ ). Inserting $1, 2, 1$ : $P$ becomes row one $11$ ? Insert $1$ : row $1$ . Insert $2$ : row $12$ . Insert $1$ : bumps the first entry $> 1$ , namely $2$ , so row one $11$ , row two $2$ . Then $P$ has content $(two 1 s, one 2) = (2, 1)$ = column sums $(1 + 1, 1 + 0) = (2, 1)$ . $Q$ records top entries $1, 1, 2$ at creation cells: content $(2, 1)$ = row sums $(1 + 1, 1 + 0) = (2, 1)$ . Rubric: full credit for the insertion tableau, recording tableau, and matching the contents to column/row sums.

Exercise 6 (hard, symbolic).

Prove that RSK gives the Cauchy identity $\sum_{λ} s_{λ} (x) s_{λ} (y) = \prod_{i, j} (1 - x_{i} y_{j})^{- 1}$ by tracking weights through the bijection.

Hint

Weight an $N$ -matrix $A$ by $\prod_{i, j} (x_{i} y_{j})^{a_{ij}}$ . Sum over all $A$ to get the product side; sum over $(P, Q)$ using the content bookkeeping to get the Schur side.

Answer

Assign to an $N$ -matrix $A = (a_{ij})$ the weight $\prod_{i, j} (x_{i} y_{j})^{a_{ij}}$ . Summing over all finite-support $A$ factors entrywise: $\sum_{A} \prod_{i, j} (x_{i} y_{j})^{a_{ij}} = \prod_{i, j} \sum_{a \geq 0} (x_{i} y_{j})^{a} = \prod_{i, j} (1 - x_{i} y_{j})^{- 1}$ . RSK sends $A$ to $(P, Q)$ of common shape $λ$ with $content (P) =$ column sums (the $y$ -degrees, since $Q$ records top indices $i$ giving the $x$ -degrees and $P$ holds the inserted $j$ giving the $y$ -degrees), so the weight equals $x^{content (Q)} y^{content (P)}$ . As $A$ ranges over all matrices, $(P, Q)$ ranges over all pairs of SSYT of equal shape, independently, so $\sum_{A} (\dots) = \sum_{λ} (\sum_{Q \in SSYT (λ)} x^{content (Q)}) (\sum_{P \in SSYT (λ)} y^{content (P)}) = \sum_{λ} s_{λ} (x) s_{λ} (y)$ , using the combinatorial definition $s_{λ} = \sum_{T} x^{content (T)}$ of 40.03.02. Equating the two evaluations gives the Cauchy identity. Rubric: full credit for the entrywise geometric-series factorisation, the weight tracking through RSK, and the assembly into $\sum_{λ} s_{λ} s_{λ}$ .

Exercise 7 (hard, symbolic).

State and prove Greene's theorem for $k = 2$ : the sum $λ_{1} + λ_{2}$ of the first two rows of $sh (P (σ))$ equals the maximal size $i_{2} (σ)$ of a union of two increasing subsequences of $σ$ .

Hint

A union of $k$ increasing subsequences is a subsequence with no decreasing subsequence of length $k + 1$ (Dilworth/Mirsky). Relate this to the first $k$ rows via Knuth invariance.

Answer

By Greene's theorem, $λ_{1} + \dots + λ_{k} = i_{k} (σ)$ , the largest cardinality of a union of $k$ increasing subsequences. For $k = 2$ : first, $λ_{1} + λ_{2} \leq i_{2}$ is impossible to exceed, since any two increasing subsequences inject into two rows under the insertion (each increasing run lengthens one row's growth record); and $i_{2} \leq λ_{1} + λ_{2}$ because a set partitionable into $\leq 2$ increasing chains has, by Mirsky's theorem, no decreasing subsequence of length $3$ , and such a subword inserts into a tableau of $\leq 2$ rows, of total size $\leq λ_{1} + λ_{2}$ by Knuth invariance (row insertion of a subword does not increase the first-two-row sum beyond that of the whole). The key fact is that Greene's quantity $i_{k}$ is a Knuth invariant: elementary Knuth moves $a c b \equiv c ab$ and $ba c \equiv b c a$ preserve both the $P$ -tableau and every $i_{k}$ , so $i_{k} (σ) = i_{k}$ of the reading word of $P$ , where increasing subsequences visibly fill the top $k$ rows. Hence $i_{2} (σ) = λ_{1} + λ_{2}$ . Rubric: full credit for the Knuth-invariance of $i_{k}$ , the Mirsky/Dilworth chain-cover input, and both inequalities.

Advanced results Master

The bumping rule organises into a monoid structure, a symmetry exchanging the two tableaux, a complete reading of the shape by subsequences, and the asymptotics of a random permutation.

Theorem 1 (Knuth equivalence and the plactic monoid). Two words over ${1, 2, \dots}$ have the same insertion tableau $P$ if and only if they are connected by elementary Knuth transformations: $a c b \equiv c ab$ when $a \leq b < c$ , and $ba c \equiv b c a$ when $a < b \leq c$ (applied to adjacent triples within a word). The quotient of the free monoid by these relations is the plactic monoid, and $P$ is the canonical representative of each class. Equivalently, jeu de taquin — sliding the empty cell of a skew tableau inward by the smaller-neighbour rule — computes the same $P$ from any skew filling with reading word in the class, so jeu de taquin and row insertion define one rectification operation ^{[Stanley Appendix 1]}. This is the combinatorial substrate of the Littlewood-Richardson rule developed in the co-produced 40.03.05.

Theorem 2 (the symmetry theorem). If $σ \mapsto (P, Q)$ under RSK, then $σ^{- 1} \mapsto (Q, P)$ ; in the matrix form, transposing the $N$ -matrix $A \mapsto A^{T}$ exchanges $P$ and $Q$ . Consequently the permutations fixed by inversion — the involutions of $S_{n}$ — biject with single standard Young tableaux ( $P = Q$ ), so $$ #{\sigma \in S_n : \sigma^2 = \mathrm{id}} ;=; \sum_{\lambda \vdash n} f^\lambda, $$ and the number of fixed points of $σ$ equals the number of columns of odd length in $sh (P (σ))$ . The proof is the matrix-ball (Viennot shadow) construction, which makes the $σ \leftrightarrow σ^{- 1}$ symmetry a reflection of the lattice picture across the diagonal ^{[Fulton Ch. 4]}.

Theorem 3 (Greene's theorem). For every $k \geq 1$ , the partial sums of the shape $λ = sh (P (σ))$ read off unions of monotone subsequences: $$ \lambda_1 + \cdots + \lambda_k = i_k(\sigma), \qquad \lambda_1' + \cdots + \lambda_k' = d_k(\sigma), $$ where $i_{k} (σ)$ (resp. $d_{k} (σ)$ ) is the maximal cardinality of a union of $k$ increasing (resp. decreasing) subsequences. The $k = 1$ case is Schensted's theorem; the full statement determines $λ$ entirely from the subsequence statistics of $σ$ and is invariant under Knuth equivalence ^{[Stanley §7.13]}.

Theorem 4 (longest increasing subsequence of a random permutation). Let $ℓ_{n} = is (σ)$ for $σ$ uniform in $S_{n}$ . Then $E [ℓ_{n}] \sim 2 n$ (the Ulam problem, solved by the Logan-Shepp-Vershik-Kerov limit shape of the RSK Young diagram under Plancherel measure, $P (λ) = (f^{λ})^{2} / n!$ ). The fluctuations obey the Baik-Deift-Johansson theorem: as $n \to \infty$ , $$ \frac{\ell_n - 2\sqrt{n}}{n^{1/6}} ;\xrightarrow{\ d\ }; \mathrm{TW}_2, $$ the Tracy-Widom GUE distribution, the same law governing the largest eigenvalue of a random Hermitian matrix. RSK is the bridge: $ℓ_{n} = λ_{1}$ , and Plancherel-random shapes are an integrable determinantal point process.

Synthesis. Putting these together, RSK is the single bijection from which the combinatorics, the symmetry, and the asymptotics all descend. The foundational reason is that row insertion is a Knuth-invariant operation: Theorem 1 makes the insertion tableau the normal form of the plactic monoid, so jeu de taquin, the Littlewood-Richardson rule of the co-produced 40.03.05, and the Schur-positivity of skew functions are all governed by the same elementary moves. This is exactly why the symmetry theorem of Theorem 2 holds — transposing the matrix is the diagonal reflection of Viennot's shadow lines — and why involutions biject with single tableaux, making $\sum_{λ} f^{λ}$ the involution count, dual to the $\sum_{λ} (f^{λ})^{2} = n!$ of the bijection itself. Greene's theorem generalises Schensted's first-row reading to the whole shape, and the bridge to analysis is the Plancherel measure $(f^{λ})^{2} / n!$ that RSK pushes forward from the uniform permutation: the Logan-Shepp-Vershik-Kerov limit shape and the Baik-Deift-Johansson Tracy-Widom fluctuations are the central insight that the longest increasing subsequence is an eigenvalue in disguise, tying this purely combinatorial rule to random-matrix theory. The same content bookkeeping that proves the Cauchy identity of 40.03.03 is the generating function of this measure, and the Frobenius characteristic of the co-produced 40.03.06 reads $\sum_{λ} (f^{λ})^{2} = n!$ as the decomposition of $C [S_{n}]$ .

Full proof set Master

Proposition 1 (row insertion is well-defined and shape-additive). For a semistandard tableau $P$ and an integer $k$ , $P \leftarrow k$ is a semistandard tableau whose shape is that of $P$ with one cell added, and the bump path moves weakly left as it descends.

Proof. Induct on the number of rows touched. In row $1$ , either $k$ appends at the right (the row stays weakly increasing, no column below is created above an existing cell, so column-strictness is vacuous for the new corner) or $k$ replaces the leftmost entry $w > k$ at column $j$ ; then row $1$ remains weakly increasing because $k$ is at least the entry to its left (that entry was $\leq k$ , being not $> k$ ) and strictly less than $w$ and all to $w$ 's right. The bumped $w$ inserts into row $2$ ; since $w$ was at column $j$ of row $1$ and the entry below it (if any) was $> w$ , $w$ 's insertion point in row $2$ is at column $\leq j$ , giving the weak-left descent and preserving column-strictness (the new entry in row $2$ at column $j^{'}$ is $\leq$ the old entry there and $>$ the entry above-left). The recursion terminates when a row appends, adding exactly one corner cell. The resulting filling is row-weak and column-strict throughout. $□$

Proposition 2 (RS is a bijection). The map $σ \mapsto (P (σ), Q (σ))$ is a bijection $S_{n} \to ⨆_{λ ⊢ n} SYT (λ)^{2}$ .

Proof. Construct the two-sided inverse by reverse insertion. Given $(P, Q) \in SYT (λ)^{2}$ , the cell $c$ holding $n$ in $Q$ is an outer corner; let $w$ be the entry of $P$ at $c$ . Reverse-bump $w$ : delete $c$ , and moving up from row $row (c)$ , in the row above find the rightmost entry $u < w$ , place $w$ in $u$ 's cell, set $w := u$ , and continue to row $1$ ; the value ejected from row $1$ is $σ (n)$ . The reverse step inverts a forward step: a forward insertion's bump path is strictly increasing in the bumped values and weakly left-descending (Proposition 1), so the rightmost-smaller search in row $i - 1$ recovers exactly the cell from which the forward path entered row $i$ . After ejecting $σ (n)$ , $(P^{'}, Q^{'})$ on shape $λ ∖ c$ is a smaller equal-shape pair; downward induction on $n$ yields $σ (n - 1), \dots, σ (1)$ , all distinct (an outer-corner deletion never repeats a value). Forward $\circ$ reverse and reverse $\circ$ forward are identities, so the map is bijective. Equating cardinalities, $n! = \sum_{λ ⊢ n} (f^{λ})^{2}$ . $□$

Proposition 3 (Schensted's theorem). $λ_{1} = is (σ)$ and $λ_{1}^{'} = ds (σ)$ , where $λ = sh (P (σ))$ .

Proof. Maintain the invariant: after inserting a prefix, the entry at cell $(1, j)$ of $P$ is the least possible final term of an increasing subsequence of length $j$ in that prefix. Base $j = 1$ holds. Inductive step: inserting $a$ , if $a$ lands at $(1, j)$ it bumped an entry $> a$ , and $a$ extends a length- $(j - 1)$ increasing subsequence ending at $(1, j - 1) \leq a$ , so the least length- $j$ tail is updated to $a$ ; if $a$ appends at the new corner $(1, λ_{1} + 1)$ , it creates a length- $(λ_{1} + 1)$ subsequence, increasing $λ_{1}$ . The invariant persists, so at the end $λ_{1}$ is the greatest $j$ admitting an increasing subsequence of length $j$ , i.e. $is (σ)$ . For $λ_{1}^{'}$ : row insertion of $σ$ and column insertion are related by transposition of $P$ , and column insertion's first-column invariant tracks decreasing subsequences; alternatively $ds (σ) = is (σ^{#})$ where $σ^{#}$ reverses the values, and the RSK shape of $σ^{#}$ is $λ^{'}$ (a known consequence of the symmetry between row/column insertion). Either way $λ_{1}^{'} = ds (σ)$ . $□$

Proposition 4 (symmetry theorem). If $σ \mapsto (P, Q)$ then $σ^{- 1} \mapsto (Q, P)$ .

Proof. Encode $σ$ as the permutation matrix with a ball at $(i, σ (i))$ , and run Viennot's shadow-line construction: the first family of shadow lines (lower-left light from the southwest) records, by their northeast corners, the first row of $P$ from the $x$ -coordinates and the first row of $Q$ from the $y$ -coordinates; iterating on the remaining balls builds successive rows. Inverting $σ$ reflects every ball across the main diagonal $(i, σ (i)) \mapsto (σ (i), i)$ , which swaps the roles of the $x$ - and $y$ -coordinates throughout the shadow construction, hence exchanges $P$ (read from one coordinate) and $Q$ (read from the other) while preserving the common shape. Therefore $σ^{- 1} \mapsto (Q, P)$ . Setting $σ = σ^{- 1}$ forces $P = Q$ , so involutions biject with single SYT and their number is $\sum_{λ ⊢ n} f^{λ}$ ; the fixed points of $σ$ are the cells of $P$ not paired by a $2$ -cycle of the shadow involution, which are the odd-length columns. $□$

Proposition 5 (Cauchy identity by RSK). $λ \sum s_{λ} (x) s_{λ} (y) = i, j \prod (1 - x_{i} y_{j})^{- 1}$ .

Proof. Weight an $N$ -matrix $A = (a_{ij})$ of finite support by $w (A) = \prod_{i, j} (x_{i} y_{j})^{a_{ij}}$ . The total weight factors as a geometric product: $\sum_{A} w (A) = \prod_{i, j} \sum_{a \geq 0} (x_{i} y_{j})^{a} = \prod_{i, j} (1 - x_{i} y_{j})^{- 1}$ , the right side. RSK is a weight-preserving bijection $A \leftrightarrow (P, Q)$ with $P, Q \in SSYT (λ)$ , where the inserted entries (column indices $j$ ) build $P$ with $content (P) =$ column sums of $A$ (the $y$ -exponents), and the recorded top indices $i$ build $Q$ with $content (Q) =$ row sums (the $x$ -exponents). Thus $w (A) = x^{content (Q)} y^{content (P)}$ . Because RSK is a bijection onto all pairs of equal-shape SSYT with $P$ and $Q$ independent, summing the weights regroups as $\sum_{λ} (\sum_{Q \in SSYT (λ)} x^{content (Q)}) (\sum_{P \in SSYT (λ)} y^{content (P)}) = \sum_{λ} s_{λ} (x) s_{λ} (y)$ by the combinatorial definition of $s_{λ}$ in 40.03.02. The two evaluations of $\sum_{A} w (A)$ coincide, giving the identity; the $0/1$ -matrix restriction with column insertion yields the dual $\prod_{i, j} (1 + x_{i} y_{j}) = \sum_{λ} s_{λ} (x) s_{λ^{'}} (y)$ identically. $□$

Connections Master

This unit is built directly on the semistandard and standard Young tableaux and the combinatorial Schur function $s_{λ} = \sum_{T} x^{content (T)}$ of 40.03.02: row insertion is an operation on exactly those tableaux, the RS bijection lands in pairs of standard tableaux of a common shape, and the RSK content bookkeeping (column sums to $content (P)$ , row sums to $content (Q)$ ) is what turns the bijection into a Schur-function identity. The first-row/first-column readings of Schensted's theorem use the shape $λ$ and conjugate $λ^{'}$ defined there.
The Cauchy identity $\sum_{λ} s_{λ} (x) s_{λ} (y) = \prod_{i, j} (1 - x_{i} y_{j})^{- 1}$ and the dual $\prod_{i, j} (1 + x_{i} y_{j}) = \sum_{λ} s_{λ} (x) s_{λ^{'}} (y)$ , of which RSK and dual RSK are the bijective proofs, are the subject of the co-produced 40.03.03, where they are derived from the Hall inner product and used to prove the orthonormality $⟨ s_{λ}, s_{μ} ⟩ = δ_{λ μ}$ ; the Knuth equivalence and jeu de taquin developed in Advanced results are the engine of the Littlewood-Richardson rule of the co-produced 40.03.05; and the Frobenius characteristic of the co-produced 40.03.06 reads the bijection's enumerative shadow $\sum_{λ} (f^{λ})^{2} = n!$ as the decomposition of the group algebra $C [S_{n}]$ .
The identity $\sum_{λ ⊢ n} (f^{λ})^{2} = n!$ is the combinatorial face of the representation theory of the symmetric group: $f^{λ} = dim S^{λ}$ is the dimension of the Specht module of 07.05.03 (so RS is the bijective shadow of $C [S_{n}] ≅ ⨁_{λ} End (S^{λ})$ ), the Young diagrams indexing the tableaux are the irreducibles of 07.05.02, and the bumping that defines insertion is the combinatorial core of Schur-Weyl duality 07.05.04. The longest-increasing-subsequence asymptotics connect this combinatorics to the random-matrix Tracy-Widom law and to the determinantal point processes that recur across mathematical physics.

Historical & philosophical context Master

The insertion algorithm was first written down by Gilbert de Beauregard Robinson in a 1938 paper on the representation theory of the symmetric group, as an auxiliary device in an attempted proof of the Littlewood-Richardson rule; it was rediscovered and turned into a clean bijective algorithm with the longest-increasing-subsequence application by Craige Schensted in his 1961 Canadian Journal of Mathematics paper ^{[Schensted 1961]}, from which the bumping procedure and Schensted's theorem take their modern form. Donald Knuth, in a 1970 Pacific Journal of Mathematics paper ^{[Knuth 1970]}, generalised the correspondence from permutations to arbitrary nonnegative integer matrices, identified the elementary word relations (now the Knuth relations) that characterise the insertion tableau, and connected the construction to the Cauchy identity for Schur functions; the three-name attribution Robinson-Schensted-Knuth dates from this work.

Curtis Greene's 1974 theorem ^{[Greene 1974]} in the Journal of Combinatorial Theory showed that the entire shape, not just its first row, is read off by unions of increasing and decreasing subsequences, completing Schensted's partial result. Marcel-Paul Schützenberger supplied the symmetry theorem and the jeu-de-taquin theory in the 1960s-70s, and Alain Lascoux and Schützenberger isolated the plactic monoid (1981) as the algebraic home of Knuth equivalence. The asymptotic study of the longest increasing subsequence of a random permutation began with Stanisław Ulam's question; the leading order $2 n$ was established through the limit-shape results of Logan and Shepp and independently Vershik and Kerov (1977), and the Tracy-Widom fluctuation law was proved by Jinho Baik, Percy Deift, and Kurt Johansson in their 1999 paper in the Journal of the American Mathematical Society ^{[Baik-Deift-Johansson 1999]}, identifying the combinatorial statistic with the largest eigenvalue of a random Hermitian matrix.

Bibliography Master

@book{stanley1999ec2,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 2},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {62},
  publisher = {Cambridge University Press},
  year      = {1999}
}

@book{fulton1997young,
  author    = {Fulton, William},
  title     = {Young Tableaux: With Applications to Representation Theory and Geometry},
  series    = {London Mathematical Society Student Texts},
  volume    = {35},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@book{sagan2001symmetric,
  author    = {Sagan, Bruce E.},
  title     = {The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions},
  series    = {Graduate Texts in Mathematics},
  volume    = {203},
  edition   = {2},
  publisher = {Springer},
  year      = {2001}
}

@article{schensted1961,
  author  = {Schensted, Craige},
  title   = {Longest increasing and decreasing subsequences},
  journal = {Canadian Journal of Mathematics},
  volume  = {13},
  pages   = {179--191},
  year    = {1961}
}

@article{knuth1970,
  author  = {Knuth, Donald E.},
  title   = {Permutations, matrices, and generalized Young tableaux},
  journal = {Pacific Journal of Mathematics},
  volume  = {34},
  pages   = {709--727},
  year    = {1970}
}

@article{greene1974,
  author  = {Greene, Curtis},
  title   = {An extension of Schensted's theorem},
  journal = {Advances in Mathematics},
  volume  = {14},
  pages   = {254--265},
  year    = {1974}
}

@article{robinson1938,
  author  = {Robinson, Gilbert de B.},
  title   = {On the representations of the symmetric group},
  journal = {American Journal of Mathematics},
  volume  = {60},
  number  = {3},
  pages   = {745--760},
  year    = {1938}
}

@article{baikdeiftjohansson1999,
  author  = {Baik, Jinho and Deift, Percy and Johansson, Kurt},
  title   = {On the distribution of the length of the longest increasing subsequence of random permutations},
  journal = {Journal of the American Mathematical Society},
  volume  = {12},
  number  = {4},
  pages   = {1119--1178},
  year    = {1999}
}

@article{logansheppshepp1977,
  author  = {Logan, Benjamin F. and Shepp, Larry A.},
  title   = {A variational problem for random Young tableaux},
  journal = {Advances in Mathematics},
  volume  = {26},
  number  = {2},
  pages   = {206--222},
  year    = {1977}
}

Prerequisites

40.03.02

Tier anchors

beginner: Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) §7.11 opening (row insertion / bumping by worked example, the Robinson-Schensted insertion and recording tableaux on a small permutation); Sagan 2001 *The Symmetric Group* 2e (Springer) §3.1-3.2 (the Robinson-Schensted map by example, longest increasing subsequence)
intermediate: Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.11 (row insertion, the RS bijection $S_n \leftrightarrow \bigsqcup_\lambda \mathrm{SYT}(\lambda)^2$, the symmetry theorem $\sigma \mapsto (P,Q) \Rightarrow \sigma^{-1} \mapsto (Q,P)$, Schensted's theorem on longest increasing/decreasing subsequences) and §7.11-7.12 (the RSK generalisation to $\mathbb{N}$-matrices and the Cauchy identity); Fulton 1997 *Young Tableaux* (Cambridge LMS Student Texts 35) Ch. 1, 4 (bumping, the RS and RSK correspondences, the symmetry theorem)
master: Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.11-7.14, Appendix 1 (RSK and dual RSK, the Cauchy and dual Cauchy identities as bijective consequences, Greene's theorem, Knuth equivalence and the plactic monoid, the symmetry theorem of Schützenberger); Knuth 1970 *Pacific J. Math.* 34 (the RSK generalisation to matrices); Schensted 1961 *Canad. J. Math.* 13 (longest increasing subsequences); Greene 1974 *J. Combin. Theory A* 14 (the shape via increasing subsequences); Sagan 2001 *The Symmetric Group* 2e Ch. 3; Baik-Deift-Johansson 1999 *J. Amer. Math. Soc.* 12 (the Tracy-Widom limit of the longest increasing subsequence)

References

Stanley, R. P. — Enumerative Combinatorics, Volume 2 · Cambridge Studies in Advanced Mathematics 62 (1999). Chapter 7 §7.11 defines Schensted row insertion (bumping): to insert $k$ into a semistandard tableau $P$, place $k$ at the end of the first row if it weakly exceeds every entry, else bump the leftmost entry strictly greater than $k$, displacing it into the next row and recursing. The Robinson-Schensted correspondence is the bijection $\sigma \leftrightarrow (P, Q)$ between permutations of $[n]$ and pairs of standard Young tableaux of the same shape $\lambda \vdash n$, where $P$ (the insertion tableau) is built by inserting $\sigma(1), \dots, \sigma(n)$ and $Q$ (the recording tableau) marks the cell added at each step. The RSK generalisation (§7.11-7.12) is a bijection between $\mathbb{N}$-matrices $A$ of finite support and pairs $(P,Q)$ of SSYT of the same shape, with $\mathrm{content}(P)$ the column sums and $\mathrm{content}(Q)$ the row sums; restricting to $0/1$-matrices gives the dual RSK with $(P, Q)$ of conjugate-compatible shapes. The symmetry theorem $\sigma \mapsto (P,Q) \Rightarrow \sigma^{-1} \mapsto (Q,P)$ (Schützenberger) implies involutions correspond to single SYT, so the number of involutions in $S_n$ equals $\sum_{\lambda \vdash n} f^\lambda$. Schensted's theorem: the length of the longest increasing subsequence of $\sigma$ is $\lambda_1$ (the first row of $P$) and the longest decreasing is $\lambda_1'$ (the first column); Greene's theorem refines this via $k$-fold unions of increasing/decreasing subsequences giving $\lambda_1 + \cdots + \lambda_k$ and $\lambda_1' + \cdots + \lambda_k'$. The Cauchy identity $\sum_\lambda s_\lambda(x) s_\lambda(y) = \prod_{i,j}(1 - x_i y_j)^{-1}$ is the generating-function shadow of RSK (and $\prod(1 + x_i y_j) = \sum_\lambda s_\lambda(x) s_{\lambda'}(y)$ of dual RSK). Knuth equivalence, the plactic monoid, and jeu de taquin appear in §7.13 and Appendix 1; Greene's theorem and the Schützenberger involution in §7.13.
Fulton, W. — Young Tableaux: With Applications to Representation Theory and Geometry · Cambridge University Press, London Mathematical Society Student Texts 35 (1997). Chapter 1 develops row bumping and the Robinson-Schensted-Knuth correspondence from the ground up: the insertion algorithm, the recording tableau, the reverse (de-insertion) algorithm proving bijectivity, and the matrix-ball construction making the symmetry $\sigma \leftrightarrow \sigma^{-1}$ transparent. Knuth equivalence on words (the elementary Knuth relations $acb \equiv cab$ for $a \le b < c$ and $bac \equiv bca$ for $a < b \le c$) and the plactic monoid are developed alongside, with the theorem that two words are Knuth-equivalent iff they have the same insertion tableau $P$; jeu de taquin (sliding) gives an equivalent description of the $P$-tableau of a skew word. Chapter 4 connects RSK to the Pieri and Littlewood-Richardson rules and to the Cauchy identities and Schur-function bases.
Sagan, B. E. — The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions · Springer Graduate Texts in Mathematics 203, 2nd edition (2001). Chapter 3 treats the Robinson-Schensted-Knuth correspondence as a combinatorial algorithm: row insertion and the RS map (§3.1-3.2), the proof of bijectivity via reverse insertion, Schensted's theorem on longest increasing and decreasing subsequences (§3.3), the symmetry $\sigma \mapsto (P,Q) \Rightarrow \sigma^{-1} \mapsto (Q,P)$ and its corollary on involutions, Greene's theorem (§3.4), and Knuth equivalence with the plactic relations and jeu de taquin (§3.5-3.6). The identity $\sum_{\lambda \vdash n} (f^\lambda)^2 = n!$ is the enumerative shadow of the RS bijection, paralleling the representation-theoretic $\sum (\dim V_\lambda)^2 = |S_n|$.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m