---
tag: 1SCF8X47G1
kind: statement
role: theorem
name: Robinson–Schensted correspondence
msc: [05A05, "05E10"]
uses: [Q6TH9PH2R7, 05RWFKVTJ7, 0515A6D2Y1, 0JV30XN73Z]
about: [Q6TH9PH2R7, 05RWFKVTJ7]
sources:
  - url: https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_correspondence
same_as:
  wikidata: Q2997917
  wikipedia: Robinson–Schensted correspondence
---

## Statement

Let $n \ge 1$ and let $S_n$ be the [[symmetric group|0515A6D2Y1]] of [[permutations|05RWFKVTJ7]] of $\set{1, \dots, n}$.
Row insertion defines a map $\sigma \mapsto (P(\sigma), Q(\sigma))$ from $S_n$ to pairs of standard [[Young tableaux|Q6TH9PH2R7]] of the same shape, a [[partition|0JV30XN73Z]] of $n$.

1. This map is a bijection onto the set of all pairs $(P, Q)$ of standard Young tableaux of the same shape with $n$ cells.
2. For every $\sigma \in S_n$, $P(\sigma^{-1}) = Q(\sigma)$ and $Q(\sigma^{-1}) = P(\sigma)$.
3. The length of the first row of the common shape equals the length of a longest increasing subsequence of $\sigma(1), \dots, \sigma(n)$.
4. The number of rows of the common shape equals the length of a longest decreasing subsequence of $\sigma(1), \dots, \sigma(n)$.

## Remarks

Row insertion of a number $x$ into a tableau works as follows.
If $x$ is larger than every entry of the first row, put $x$ at the end of that row.
Otherwise $x$ replaces the smallest entry of the row that is larger than $x$, and the replaced entry is inserted into the next row in the same way.
The tableau $P(\sigma)$ is obtained by inserting $\sigma(1), \dots, \sigma(n)$ in order into the empty tableau.
The tableau $Q(\sigma)$ records the step: it has entry $k$ in the cell that was created at step $k$.
Each step can be undone from the position of the new cell, which gives the inverse map and proves part 1.
Parts 3 and 4 are due to Schensted.

Example: for $\sigma = 2\,3\,1$ in one-line notation, inserting $2$ and $3$ gives the row $2\,3$.
Inserting $1$ bumps $2$ into the second row, so $P = \begin{smallmatrix} 1 & 3 \\ 2 & \end{smallmatrix}$ and $Q = \begin{smallmatrix} 1 & 2 \\ 3 & \end{smallmatrix}$.
The first row has length $2$, the length of the increasing subsequence $2\,3$.

## Explanations

### L1 human

The correspondence turns a permutation into two tableaux of the same shape, and back again without loss.
It is like a card-sorting game in which each new card pushes a bigger card down to the next row.
The shape you end with records how long the increasing and decreasing runs hidden in the permutation can be.

### L2 human

Counting both sides of part 1 gives $\sum_{\lambda \vdash n} (f^\lambda)^2 = n!$, where $f^\lambda$ is the number of standard tableaux of shape $\lambda$.
This matches the identity that the squares of the dimensions of the irreducible representations of $S_n$ add up to $\abs{S_n}$.
By part 2, involutions correspond to single tableaux, so the number of involutions in $S_n$ is $\sum_{\lambda \vdash n} f^\lambda$.
The [[Robinson–Schensted–Knuth correspondence|8JW8F4VVED]] extends the bijection to matrices with nonnegative integer entries and semistandard tableaux.