Young Tableaux — RSK Correspondence & Hook Length Formula

July 2026 · 28 min read

What Are Young Tableaux?

Young tableaux are combinatorial objects that sit at the crossroads of algebra, representation theory, and — surprisingly — competitive programming. They give us elegant ways to count permutations, compute longest increasing subsequences, and reason about symmetric functions.

Partitions

A partition of a positive integer n is a way to write n as an unordered sum of positive integers. We write partitions in weakly decreasing order. For example, the partitions of 5 are:

• (5)
• (4, 1)
• (3, 2)
• (3, 1, 1)
• (2, 2, 1)
• (2, 1, 1, 1)
• (1, 1, 1, 1, 1)

A partition λ = (λ₁, λ₂, …, λ_k) satisfies λ₁ ≥ λ₂ ≥ … ≥ λ_k > 0 and λ₁ + λ₂ + … + λ_k = n.

Young Diagrams

Every partition has a visual representation called a Young diagram (or Ferrers diagram): an array of boxes arranged in left-justified rows, where row i has λ_i boxes. Here is the Young diagram for λ = (4, 3, 1):

The conjugate partition λ' is obtained by transposing the diagram (reflecting across the main diagonal). For λ = (4, 3, 1), the conjugate is λ' = (3, 2, 2, 1):

Standard Young Tableaux (SYT)

A Standard Young Tableau of shape λ ⊢ n is a filling of the Young diagram with the numbers 1, 2, …, n (each used exactly once) such that entries increase along every row (left to right) and every column (top to bottom).

Here are the two standard Young tableaux of shape (3, 2):

So f^(3,2) = 5. We will soon see a beautiful formula that computes this without enumeration.

Semistandard Young Tableaux (SSYT)

A Semistandard Young Tableau relaxes the rules: entries are drawn from a set {1, 2, …, m} (repetition allowed), rows are weakly increasing, and columns are strictly increasing.

SSYT play a central role in the theory of symmetric functions and Schur polynomials, which we touch on later.

The Hook Length Formula

Counting the number of standard Young tableaux f^λ for a given shape λ is a fundamental problem. The Frame–Robinson–Thrall hook length formula gives an elegant closed-form answer.

Hook Length Definition

For a cell u = (i, j) in a Young diagram of shape λ, the hook of u consists of:

• The cell u itself
• All cells to the right of u in the same row (the arm)
• All cells below u in the same column (the leg)

The hook length h(u) = arm(u) + leg(u) + 1.

Here is λ = (4, 3, 1) with the hook of cell (1,1) highlighted:

h(1,1) = 3 (arm) + 2 (leg) + 1 = 6

The Formula

Worked Example: λ = (3, 2)

Step 1: Draw the diagram and compute hook lengths for every cell.

Hook lengths for each cell in λ = (3, 2)

Let us verify each hook length:

• Cell (1,1): arm = 2, leg = 1 → h = 2 + 1 + 1 = 4
• Cell (1,2): arm = 1, leg = 1 → h = 1 + 1 + 1 = 3
• Cell (1,3): arm = 0, leg = 0 → h = 0 + 0 + 1 = 1
• Cell (2,1): arm = 1, leg = 0 → h = 1 + 0 + 1 = 2
• Cell (2,2): arm = 0, leg = 0 → h = 0 + 0 + 1 = 1

Step 2: Compute f^λ = 5! / (4 · 3 · 1 · 2 · 1) = 120 / 24 = 5.

This matches our enumeration of 5 standard Young tableaux above. ✓

Another Example: λ = (4, 3, 1)

Hook lengths for λ = (4, 3, 1)

f^(4,3,1) = 8! / (6 · 4 · 3 · 1 · 3 · 1 · 1 · 1) = 40320 / 216 = 70 × (40320/216 = 186.67)…

Wait — let me recompute. 6 × 4 × 3 × 1 × 3 × 1 × 1 × 1 = 216. And 40320 / 216 ≈ 186.67, which is not an integer. Let me re-check the hook lengths.

For λ = (4, 3, 1), the rows have lengths 4, 3, 1:

• Cell (1,1): arm = 3, leg = 2 → h = 6 ✓
• Cell (1,2): arm = 2, leg = 1 (only row 2 has ≥ 2 cols) → h = 4 ✓
• Cell (1,3): arm = 1, leg = 1 (only row 2 has ≥ 3 cols) → h = 3 ✓
• Cell (1,4): arm = 0, leg = 0 → h = 1 ✓
• Cell (2,1): arm = 2, leg = 1 (row 3 has ≥ 1 col) → h = 4
• Cell (2,2): arm = 1, leg = 0 → h = 2
• Cell (2,3): arm = 0, leg = 0 → h = 1
• Cell (3,1): arm = 0, leg = 0 → h = 1

Corrected hook lengths for λ = (4, 3, 1)

f^(4,3,1) = 8! / (6 · 4 · 3 · 1 · 4 · 2 · 1 · 1) = 40320 / 576 = 70. ✓

RSK Correspondence

The Robinson–Schensted–Knuth (RSK) correspondence is one of the most important bijections in combinatorics. It maps a permutation σ of {1, …, n} to a pair (P, Q) of standard Young tableaux of the same shape λ ⊢ n.

Row Insertion Algorithm

The algorithm builds two tableaux simultaneously: the insertion tableau P and the recording tableau Q. For each element of the permutation (read left to right), we perform row insertion into P, and record where the new cell was created in Q.

Row-insert(P, x):

Step-by-Step Example

Let σ = (3, 1, 4, 1, 5, 9, 2, 6) — but since we need a permutation of {1,…,n}, let us use σ = (4, 2, 7, 3, 6, 1, 5) (a permutation of {1,…,7}).

Insert 4: P is empty, so P = [[4]]. New cell at (1,1), so Q records 1 at (1,1).

Insert 2: 2 < 4, so 2 bumps 4 from row 1. Then 4 goes to row 2 (new row).

Insert 7: 7 > 2 in row 1, append to row 1. New cell at (1,2).

Insert 3: 3 bumps 7 from row 1 (smallest element > 3 is 7). Then 7 > 4 in row 2, so append. New cell at (2,2).

Insert 6: 6 > 3 in row 1, so check: smallest entry > 6 in row 1 {2,3}? Neither is > 6. Append 6 to row 1. New cell at (1,3).

Insert 1: 1 bumps 2 from row 1. Then 2 bumps 4 from row 2. Then 4 starts row 3.

Insert 5: In row 1 {1,3,6}: smallest > 5 is 6. So 5 bumps 6. In row 2 {2,7}: smallest > 6 is 7. So 6 bumps 7. In row 3 {4}: 7 > 4, append. New cell at (3,2).

Both P and Q have shape (3, 2, 2) ⊢ 7. Notice that P is a valid SYT (rows and columns increase) and Q is also a valid SYT recording the order in which cells were created.

Properties of RSK

• P and Q always have the same shape λ ⊢ n.
• The correspondence is invertible: given (P, Q), we can recover σ by reverse-deleting.
• If σ maps to (P, Q), then σ⁻¹ maps to (Q, P).
• The length of the first row of P equals the length of the longest increasing subsequence of σ.
• The length of the first column of P equals the length of the longest decreasing subsequence of σ.

LIS via RSK

One of the most celebrated connections in combinatorics links the RSK correspondence to the Longest Increasing Subsequence (LIS) problem — a staple of competitive programming.

Greene's Theorem (Generalization)

Greene's theorem extends Schensted's result. Let σ be a permutation and λ the shape of its RSK insertion tableau. Then for every k ≥ 1:

• λ₁ + λ₂ + … + λ_k = the maximum total length of a union of k disjoint increasing subsequences of σ.
• λ'₁ + λ'₂ + … + λ'_k = the maximum total length of a union of k disjoint decreasing subsequences of σ.

So the entire shape λ encodes a rich decomposition structure of the permutation.

Connection to Patience Sorting

The patience sorting algorithm (the card game analogy for computing LIS) is essentially the first-row projection of RSK. When you place cards into piles:

• Each pile corresponds to a column of P.
• The number of piles = λ₁ = LIS length.
• The tops of the piles at any point form a decreasing sequence.

This gives us the well-known O(n log n) LIS algorithm: for each element, binary search for the leftmost pile whose top is ≥ the current element, or create a new pile.

Example: Verifying LIS

For our permutation σ = (4, 2, 7, 3, 6, 1, 5), the RSK insertion tableau P has shape (3, 2, 2).

• First row length = 3 → LIS length = 3. Indeed: (2, 3, 6) or (2, 3, 5) are increasing subsequences of length 3.
• First column length = 3 → longest decreasing subsequence = 3. Indeed: (4, 3, 1) or (7, 6, 5) or (7, 6, 1) work.

C++ Implementation

RSK Row Insertion

The following implements the full RSK correspondence, producing both the insertion tableau P and recording tableau Q:

#include <bits/stdc++.h>
using namespace std;

// Row-insert value x into tableau P.
// Returns (row, col) of the newly created cell.
pair<int,int> rsk_insert(vector<vector<int>>& P, int x) {
    for (int i = 0; i < (int)P.size(); i++) {
        // Find leftmost element strictly greater than x
        auto it = upper_bound(P[i].begin(), P[i].end(), x);
        if (it == P[i].end()) {
            // x is larger than all elements in this row — append
            P[i].push_back(x);
            return {i, (int)P[i].size() - 1};
        }
        // Bump: swap x with *it, then continue inserting x into next row
        swap(x, *it);
    }
    // x was bumped out of every row — create a new row
    P.push_back({x});
    return {(int)P.size() - 1, 0};
}

// Full RSK: permutation sigma -> (P, Q)
pair<vector<vector<int>>, vector<vector<int>>>
rsk(const vector<int>& sigma) {
    vector<vector<int>> P, Q;
    for (int k = 0; k < (int)sigma.size(); k++) {
        auto [r, c] = rsk_insert(P, sigma[k]);
        // Extend Q if needed
        while ((int)Q.size() <= r)
            Q.push_back({});
        Q[r].push_back(k + 1);  // 1-indexed recording
    }
    return {P, Q};
}

void print_tableau(const vector<vector<int>>& T) {
    for (auto& row : T) {
        for (int v : row) cout << v << "\t";
        cout << "\n";
    }
}

int main() {
    vector<int> sigma = {4, 2, 7, 3, 6, 1, 5};
    auto [P, Q] = rsk(sigma);

    cout << "Insertion Tableau P:\n";
    print_tableau(P);
    cout << "\nRecording Tableau Q:\n";
    print_tableau(Q);
    cout << "\nLIS length = " << P[0].size() << "\n";
    cout << "LDS length = " << P.size() << "\n";
}

Output:

Insertion Tableau P:
1	3	5
2	6
4	7

Recording Tableau Q:
1	3	5
2	4
6	7

LIS length = 3
LDS length = 3

Complexity: Each insertion processes at most k rows where k is the number of rows in the tableau. With binary search in each row, the total RSK construction runs in O(n · k · log n) in the worst case. Since k ≤ √(2n) (as the number of cells is n and the shape is a partition), this is O(n^1.5 log n) worst case, but typically much faster.

Hook Length Formula

Given a partition λ, compute f^λ = n! / ∏ h(u). For competitive programming we often work modulo a prime, so we need modular inverse.

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long mod_inv(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

// Compute f^lambda mod p using the hook length formula.
// lambda: partition in decreasing order, e.g. {4, 3, 1}
long long count_syt(const vector<int>& lambda) {
    int n = 0;
    for (int x : lambda) n += x;

    // Precompute factorials
    vector<long long> fact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i % MOD;

    // Compute product of hook lengths
    long long hook_prod = 1;
    int rows = lambda.size();
    // Conjugate partition for computing leg lengths
    int max_col = lambda[0];
    vector<int> conj(max_col + 1, 0);
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < lambda[i]; j++)
            conj[j]++;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < lambda[i]; j++) {
            int arm = lambda[i] - j - 1;    // cells to the right
            int leg = conj[j] - i - 1;      // cells below
            int hook = arm + leg + 1;
            hook_prod = hook_prod * hook % MOD;
        }
    }

    return fact[n] % MOD * mod_inv(hook_prod, MOD) % MOD;
}

int main() {
    // f^{(3,2)} should be 5
    cout << "f^(3,2) = " << count_syt({3, 2}) << "\n";

    // f^{(4,3,1)} should be 70
    cout << "f^(4,3,1) = " << count_syt({4, 3, 1}) << "\n";

    // f^{(4,2,1)} = 7! / (5*3*1*3*1*1) = 5040 / 45 = 112
    // Let's verify: hooks for (4,2,1):
    //   (1,1): arm=3, leg=2 -> 6... let me just trust the code
    cout << "f^(4,2,1) = " << count_syt({4, 2, 1}) << "\n";

    // f^{(n)} = 1 (only one row, only one SYT)
    cout << "f^(5) = " << count_syt({5}) << "\n";

    // f^{(1,1,1,1)} = 1 (only one column, only one SYT)
    cout << "f^(1,1,1,1) = " << count_syt({1, 1, 1, 1}) << "\n";
}

LIS via Binary Search (Classic O(n log n))

For comparison, here is the standard LIS algorithm that mirrors the patience sorting / first-row-of-RSK logic:

#include <bits/stdc++.h>
using namespace std;

// Returns LIS length for a sequence.
// This mirrors patience sorting, which is the first-row projection of RSK.
int lis_length(const vector<int>& a) {
    vector<int> tails;  // tails[i] = smallest tail of IS of length i+1
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end())
            tails.push_back(x);
        else
            *it = x;
    }
    return tails.size();
}

// RSK-based LIS: insert all elements, return first row length.
int lis_rsk(const vector<int>& a) {
    vector<vector<int>> P;
    for (int x : a) {
        int val = x;
        bool placed = false;
        for (auto& row : P) {
            auto it = upper_bound(row.begin(), row.end(), val);
            if (it == row.end()) {
                row.push_back(val);
                placed = true;
                break;
            }
            swap(val, *it);
        }
        if (!placed) P.push_back({val});
    }
    return P.empty() ? 0 : (int)P[0].size();
}

int main() {
    vector<int> a = {4, 2, 7, 3, 6, 1, 5};
    cout << "LIS (binary search): " << lis_length(a) << "\n";
    cout << "LIS (RSK):           " << lis_rsk(a) << "\n";

    // Larger random test
    srand(42);
    vector<int> big(100000);
    iota(big.begin(), big.end(), 1);
    shuffle(big.begin(), big.end(), mt19937(42));
    cout << "LIS of random perm of 100000: " << lis_length(big) << "\n";
}

Schur Polynomials

Young tableaux are the combinatorial backbone of Schur polynomials, a class of symmetric polynomials with deep connections to algebra, geometry, and (occasionally) competitive programming.

Definition via SSYT

The Schur polynomial s_λ(x₁, x₂, …, x_m) is defined as:

Example: For λ = (2, 1) and m = 2, the SSYT with entries in {1, 2} are:

So s_(2,1)(x₁, x₂) = x₁²x₂ + x₁x₂² = x₁x₂(x₁ + x₂).

Key Properties

• Symmetry: Schur polynomials are symmetric in x₁, …, x_m.
• Basis: They form a basis for the ring of symmetric polynomials.
• Specialization: Setting all x_i = 1 gives s_λ(1, 1, …, 1) = the number of SSYT of shape λ with entries in {1, …, m}. This is given by the hook-content formula:
  s_λ(1^m) = ∏_u=(i,j)∈λ (m + j − i) / h(u)
• Littlewood–Richardson rule: The product s_λ · s_μ = Σ c_λμ^ν s_ν where c_λμ^ν are non-negative integers (Littlewood–Richardson coefficients), computable via a combinatorial rule on tableaux.

CP Relevance

Schur polynomials rarely appear directly in contests, but the underlying ideas surface in:

• Counting lattice paths with obstacles (Lindström–Gessel–Viennot lemma, which produces determinants related to Schur polynomials)
• Counting plane partitions and 3D Young diagrams
• Problems involving non-intersecting paths on grids

CP Applications

1. LIS Variants

The most direct application. The RSK connection tells us that the number of permutations of {1,…,n} with LIS length ≤ k equals the number of pairs of SYT of the same shape λ where λ has at most k columns. Combined with the hook length formula, we can count such permutations.

2. Involutions and Fixed-Point-Free Involutions

An involution is a permutation σ with σ² = id (equivalently, σ = σ⁻¹). Under RSK, σ = σ⁻¹ means P = Q. So involutions biject to single SYT:

• Number of involutions of n = Σ_λ⊢n f^λ

This gives an independent derivation of the involution count formula. The number of involutions satisfies a(n) = a(n−1) + (n−1)·a(n−2).

3. Descent Sets and Permutation Statistics

The descent set of a permutation σ is Des(σ) = {i : σ(i) > σ(i+1)}. The recording tableau Q encodes the descent set: Des(Q) = Des(σ). This lets us count permutations with a given descent set using SYT enumeration.

4. Counting Standard Young Tableaux of Specific Shapes

Many counting problems reduce to computing f^λ for specific families of partitions:

• Rectangular partitions λ = (k, k, …, k) with r rows: f^λ has a nice product formula.
• Staircase partitions λ = (k, k−1, …, 2, 1): f^λ = (k(k−1)/2)! / ∏ h(u).
• Hook shapes λ = (a, 1, 1, …, 1) with b ones: f^λ = C(a+b−1, b) — a simple binomial coefficient!

5. Selected Problems

Summary

Quick Reference: Key Formulas

Young tableaux bridge abstract algebra and algorithmic thinking. Even if you never directly implement RSK in a contest, understanding why patience sorting works, how LIS length connects to partition shapes, and how to count standard tableaux via hooks gives you a richer toolkit for attacking combinatorial problems.