Wiki › Thuật toán › Toán học › Young tableau và công thức móc (hook length)

Young tableau và công thức móc (hook length)

Biểu đồ Young, bảng Young chuẩn, công thức móc để đếm số bảng, và thuật toán chèn RSK cùng định lý Greene để trả lời các câu hỏi về dãy con tăng, dãy con không tăng.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 15 phút 3 lượt xem

Biểu đồ Young (Young diagram) của một phân hoạch λ=(λ1≥λ2≥⋯≥λr>0) của số n là hình gồm r hàng ô vuông căn trái, hàng i có λi ô. Bảng Young chuẩn (standard Young tableau, SYT) là cách điền các số 1,2,…,n vào các ô sao cho mỗi hàng tăng từ trái sang phải và mỗi cột tăng từ trên xuống dưới. Hai câu hỏi kinh điển trong competitive programming:

  • Đếm số bảng Young chuẩn của một hình dạng cho trước: công thức móc (hook length formula) cho đáp án đóng fλ=n!/∏h(c), tính trong O(n) sau khi có giai thừa.
  • Phân tích một dãy số bằng thuật toán chèn RSK (Robinson-Schensted-Knuth): bảng thu được có hàng đầu dài đúng bằng dãy con tăng dài nhất (LIS), và theo định lý Greene, tổng độ dài k hàng (hoặc k cột) đầu cho kích thước lớn nhất của hợp k dãy con tăng (hoặc không tăng). Chèn một phần tử tốn O(rlogn) với r là số hàng.

Các bài đếm "số cách xếp người vào lưới sao cho hàng và cột tăng", "số hoán vị có LIS bằng k", hay "dãy con dài nhất có LIS không quá K" đều quy về hai công cụ này.

Ý tưởng / Trực giác

Móc của một ô. Với ô c ở hàng i, cột j, móc H(c) gồm chính ô đó, các ô bên phải nó trong cùng hàng (cánh tay, λi−j ô nếu đánh số cột từ 1) và các ô bên dưới nó trong cùng cột (cái chân, λj′−i ô, với λj′ là độ cao cột j). Độ dài móc

h(c)=(λi−j)+(λj′−i)+1.

Công thức móc (Frame, Robinson, Thrall 1954):

fλ=n!∏c∈λh(c).

Vì sao đúng (phác thảo). Một lý luận "gần đúng" giúp nhớ công thức: xếp ngẫu nhiên n! cách điền, ràng buộc ở ô c là "số tại c nhỏ nhất trong móc của nó", xác suất 1/h(c); nếu các ràng buộc độc lập thì ra đúng công thức. Chúng không độc lập, nhưng chứng minh chặt chẽ của Greene, Nijenhuis và Wilf dùng bước đi móc (hook walk) ngẫu nhiên: chọn một ô đều, rồi lặp lại nhảy tới một ô ngẫu nhiên khác trong móc của ô hiện tại cho tới khi tới một góc (ô không có cánh tay và chân). Họ chứng minh xác suất dừng ở góc c đúng bằng fλ−c/fλ, mà số n trong SYT luôn nằm ở một góc, nên fλ=∑c gócfλ−c (luật rẽ nhánh). Biểu thức n!/∏h thoả cùng truy hồi và cùng điều kiện đầu, nên hai bên bằng nhau.

Chèn RSK. Duy trì bảng P có mỗi hàng tăng ngặt. Để chèn x:

  1. Ở hàng 1, tìm phần tử trái nhất ≥x. Nếu không có, đặt x vào cuối hàng và dừng.
  2. Nếu có phần tử y như vậy, thay y bằng x ("đẩy" y ra), rồi chèn y vào hàng 2 theo đúng quy tắc trên, và cứ thế xuống dưới. Hết hàng thì tạo hàng mới.

Hàng 1 chính là mảng d của thuật toán LIS O(nlogn) quen thuộc (d[k] = phần tử cuối nhỏ nhất của dãy con tăng độ dài k+1), nên λ1= LIS. Mỗi lần chèn thêm đúng một ô và hình dạng luôn là biểu đồ Young (phần tử bị đẩy xuống luôn đứng ở cột không lớn hơn cột nó rời đi).

Định lý Greene. Gọi λ là hình dạng của bảng RSK của dãy a (quy tắc ≥ như trên). Khi đó với mọi k:

  • λ1+⋯+λk = kích thước lớn nhất của hợp k dãy con tăng ngặt rời nhau;
  • λ1′+⋯+λk′=∑imin(λi,k) = kích thước lớn nhất của hợp k dãy con không tăng rời nhau.

Với k=1 ta có lại: hàng đầu là LIS, cột đầu là dãy con không tăng dài nhất. Lưu ý Greene không nói các hàng của bảng là các dãy con đó (các phần tử trong một hàng nói chung không theo đúng thứ tự xuất hiện), chỉ nói về độ dài.

RSK là song ánh. Nếu đồng thời ghi lại vị trí ô mới thêm ở mỗi bước vào bảng thứ hai Q (bảng ghi), thì hoán vị ↔ cặp (P,Q) cùng hình dạng là một song ánh. Hệ quả: số hoán vị của n phần tử có bảng hình dạng λ là (fλ)2, và ∑λ(fλ)2=n!. Muốn đếm số hoán vị có LIS bằng k, ta cộng (fλ)2 trên các λ có λ1=k.

Ví dụ chạy tay

Đếm bảng chuẩn hình λ=(3,2,1). Độ dài móc từng ô:

 5 3 1
 3 1
 1

Ví dụ ô góc trái trên: cánh tay 2 ô, chân 2 ô, cộng chính nó: h=5. Tích các móc là 5·3·1·3·1·1=45, nên

f(3,2,1)=6!45=72045=16.

Kiểm tra bằng luật rẽ nhánh: (3,2,1) có ba góc, bỏ đi được (2,2,1), (3,1,1), (3,2), với f lần lượt 5,6,5; tổng 16.

Chèn RSK dãy 3,1,4,1,5,2 (có phần tử lặp, quy tắc "trái nhất ≥x"):

chèn thao tác bảng P sau bước
3 hàng 1 trống, đặt cuối [3]
1 hàng 1: 3≥1, thay 3 bằng 1, đẩy 3 xuống hàng 2 [1] / [3]
4 hàng 1: không có phần tử ≥4, đặt cuối [1 4] / [3]
1 hàng 1: 1≥1, thay, đẩy 1; hàng 2: 3≥1, thay, đẩy 3; hàng 3 mới [1 4] / [1] / [3]
5 hàng 1: đặt cuối [1 4 5] / [1] / [3]
2 hàng 1: 4≥2, thay, đẩy 4; hàng 2: không có phần tử ≥4, đặt cuối [1 2 5] / [1 4] / [3]

Bảng cuối:

 1 2 5
 1 4
 3

Hình dạng λ=(3,2,1). Đọc theo Greene:

  • λ1=3: LIS dài 3 (ví dụ 1,4,5). Lưu ý hàng 1,2,5 của bảng không phải một dãy con của dãy gốc (2 đứng sau 5).
  • λ1+λ2=5: hai dãy con tăng ngặt rời nhau phủ được 5 phần tử, ví dụ 3,4,5 và 1,2.
  • λ1′=3: dãy con không tăng dài nhất dài 3 (ví dụ 3,1,1).
  • ∑min(λi,2)=2+2+1=5: hai dãy con không tăng phủ được 5 phần tử, ví dụ 3,1,1 và 4,2. Nói cách khác, dãy con dài nhất có LIS ≤2 có 5 phần tử.

Chương trình bên dưới với đầu vào 6 3 1 4 1 5 2 in đúng bảng trên, dãy Greene 3 5 6 6 6 6 (với k=1..6) và fλ=16.

Cài đặt

Chương trình đọc n và dãy a, dựng bảng RSK, in các hàng, in với mỗi k=1..n kích thước lớn nhất của hợp k dãy con không tăng, rồi in số bảng Young chuẩn có cùng hình dạng (công thức móc, modulo 109+7).

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

const long long MOD = 1e9 + 7;

long long power(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}

// Số bảng Young chuẩn hình dạng lam (lam[0] >= lam[1] >= ...), theo công thức móc:
// f = n! / tích độ dài móc, tính modulo MOD (MOD nguyên tố > n)
long long hook_count(const vector<int>& lam) {
    int rows = lam.size();
    if (rows == 0) return 1;
    vector<int> col(lam[0], 0);          // col[j] = độ cao cột j (dạng liên hợp)
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < lam[i]; j++) col[j]++;
    long long n = 0, prod = 1;
    for (int i = 0; i < rows; i++) {
        n += lam[i];
        for (int j = 0; j < lam[i]; j++) {
            int hook = (lam[i] - j - 1) + (col[j] - i - 1) + 1;   // tay + chân + chính ô
            prod = prod * hook % MOD;
        }
    }
    long long fact = 1;
    for (long long i = 2; i <= n; i++) fact = fact * i % MOD;
    return fact * power(prod, MOD - 2) % MOD;
}

// Chèn hàng RSK: mỗi hàng tăng ngặt, ở mỗi hàng tìm phần tử trái nhất >= x,
// thay nó bằng x rồi đẩy phần tử bị thay xuống hàng dưới
void rsk_insert(vector<vector<int>>& P, int x) {
    for (auto& row : P) {
        auto it = lower_bound(row.begin(), row.end(), x);   // trái nhất >= x
        if (it == row.end()) {
            row.push_back(x);
            return;
        }
        swap(*it, x);                                     // x bị đẩy xuống hàng sau
    }
    P.push_back({x});                                     // tạo hàng mới
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> P;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        rsk_insert(P, x);
    }
    vector<int> lam;
    for (auto& row : P) {
        lam.push_back(row.size());
        for (int v : row) cout << v << ' ';
        cout << '\n';
    }
    // Greene: hợp lớn nhất của k dãy con không tăng = tổng min(lam_i, k)
    for (int k = 1; k <= n; k++) {
        int s = 0;
        for (int L : lam) s += min(L, k);
        cout << s << (k < n ? ' ' : '\n');
    }
    cout << hook_count(lam) << '\n';
}
Python
import sys
from bisect import bisect_left

MOD = 10**9 + 7


# Số bảng Young chuẩn hình dạng lam (lam[0] >= lam[1] >= ...), theo công thức móc:
# f = n! / tích độ dài móc, tính modulo MOD (MOD nguyên tố > n)
def hook_count(lam):
    if not lam:
        return 1
    col = [0] * lam[0]  # col[j] = độ cao cột j (dạng liên hợp)
    for L in lam:
        for j in range(L):
            col[j] += 1
    n, prod = 0, 1
    for i, L in enumerate(lam):
        n += L
        for j in range(L):
            hook = (L - j - 1) + (col[j] - i - 1) + 1  # tay + chân + chính ô
            prod = prod * hook % MOD
    fact = 1
    for i in range(2, n + 1):
        fact = fact * i % MOD
    return fact * pow(prod, MOD - 2, MOD) % MOD


# Chèn hàng RSK: mỗi hàng tăng ngặt, ở mỗi hàng tìm phần tử trái nhất >= x,
# thay nó bằng x rồi đẩy phần tử bị thay xuống hàng dưới
def rsk_insert(P, x):
    for row in P:
        i = bisect_left(row, x)  # trái nhất >= x
        if i == len(row):
            row.append(x)
            return
        row[i], x = x, row[i]  # x bị đẩy xuống hàng sau
    P.append([x])  # tạo hàng mới


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    P = []
    for i in range(n):
        rsk_insert(P, int(data[1 + i]))
    lam = [len(row) for row in P]
    out = [" ".join(map(str, row)) + " " for row in P]
    # Greene: hợp lớn nhất của k dãy con không tăng = tổng min(lam_i, k)
    out.append(" ".join(str(sum(min(L, k) for L in lam)) for k in range(1, n + 1)))
    out.append(str(hook_count(lam)))
    print("\n".join(out))


main()

Muốn quy tắc cho dãy con không giảm (thay vì tăng ngặt) thì đổi lower_bound thành upper_bound (bisect_left thành bisect_right): tìm phần tử trái nhất >x. Khi đó hàng đầu là dãy con không giảm dài nhất và các cột ứng với dãy con giảm ngặt.

Độ phức tạp

Thao tác Thời gian Bộ nhớ
Công thức móc cho hình λ có n ô O(n+logMOD) O(λ1)
Chèn một phần tử vào bảng RSK có r hàng O(rlogn)
Dựng toàn bộ bảng RSK của dãy độ dài n O(n·rlogn), xấu nhất O(n2logn) O(n)
Chỉ giữ L hàng đầu O(nLlogn) O(n)

Vì sao công thức móc là O(n)? Mỗi ô tính móc trong O(1) nhờ mảng độ cao cột; giai thừa O(n); một lần nghịch đảo modulo O(logMOD).

Vì sao RSK có thể chậm? Một lần chèn có thể đẩy dây chuyền qua mọi hàng; dãy giảm dần tạo ra n hàng nên tổng là O(n2) lần tìm kiếm nhị phân. Mẹo cắt cụt: L hàng đầu của bảng chỉ phụ thuộc vào chính chúng (phần tử bị đẩy khỏi hàng L không bao giờ quay lại), nên nếu câu hỏi chỉ cần λ1,…,λL thì bỏ hẳn phần dưới. Cần các cột đầu thì dựng bảng của dãy đảo dấu −a với quy tắc ngược lại: các cột của bảng này trở thành hàng.

⚠️ Lỗi thường gặp

  • Nhầm quy tắc ≥ và > khi có phần tử lặp: lower_bound cho hàng tăng ngặt (LIS tăng ngặt, cột ứng với dãy không tăng), upper_bound cho hàng không giảm. Dùng nhầm chỉ sai khi dãy có giá trị lặp, nên test hoán vị không phát hiện được.
  • Coi các hàng của bảng là các dãy con thật: Greene chỉ khẳng định về độ dài. Hàng 1,2,5 trong ví dụ không phải dãy con của 3,1,4,1,5,2. Muốn khôi phục dãy con cụ thể phải lưu vết như thuật toán LIS thường.
  • Tính móc sai do đánh số: với chỉ số từ 0, h=(λi−j−1)+(λj′−i−1)+1. Quên −1 ở tay hoặc chân là nhầm phổ biến nhất; kiểm tra nhanh bằng hình một hàng (n) (phải ra f=1) và hình (2,1) (phải ra f=2).
  • Chia modulo khi MOD≤n: công thức chia cho tích các móc, mỗi móc ≤n. Nếu modulo nhỏ hơn hoặc bằng n (hoặc không nguyên tố) thì không nghịch đảo được; khi đó phân tích thừa số nguyên tố của n! và các móc rồi trừ số mũ.
  • Quên rằng fλ chỉ đếm bảng chuẩn: số bảng nửa chuẩn (cho phép lặp số, hàng không giảm, cột tăng ngặt) với giá trị trong [1,m] dùng công thức móc-nội dung khác: ∏cm+j−ih(c) (với j−i là nội dung của ô). Dùng nhầm công thức là sai hoàn toàn.
  • Dựng bảng đầy đủ khi chỉ cần vài hàng: dãy gần giảm tạo ra Θ(n) hàng và RSK đầy đủ thành O(n2logn). Hãy cắt cụt số hàng theo đúng nhu cầu của câu hỏi.

Biến thể / Mở rộng

  • Đếm hoán vị theo LIS: nhờ song ánh RSK, số hoán vị có LIS đúng bằng k là ∑λ⊢n, λ1=k(fλ)2; duyệt phân hoạch của n nhỏ là đủ. Số hoán vị tự nghịch đảo (involution) có hình λ là fλ.
  • Công thức móc-nội dung cho bảng nửa chuẩn, và công thức móc cho các hình "lệch" (shifted) hay cây (đếm số cách gán nhãn tăng dần trên cây: n!/∏vsize(v), cùng ý tưởng móc).
  • Đếm với tổ hợp: cách tính giai thừa, nghịch đảo modulo và đếm cơ bản xem ở Tổ hợp và đếm cơ bản; hình chữ nhật 2×n cho đúng số Catalan f(n,n)=1n+1(2nn).
  • Kết hợp truy vấn offline: câu hỏi theo tiền tố của dãy có thể xử lý bằng cách chèn dần và trả lời theo thứ tự, xem Xử lý truy vấn offline.
  • Dilworth và Mirsky: "dãy có LIS ≤K" tương đương "phân hoạch được thành K dãy không tăng"; đây là dạng đặc biệt của định lý Dilworth cho tập sắp thứ tự bộ phận, cũng có thể giải bằng ghép cặp hai phía trên đồ thị so sánh khi n nhỏ.

Bài tập luyện

  • Domino cho biểu đồ Young (youngdom): (Very Hard) Đặt nhiều quân domino rời nhau nhất vào một biểu đồ Young cho bởi độ cao các cột. Tô biểu đồ theo kiểu bàn cờ; tính chất "cột không tăng" của biểu đồ Young bảo đảm cận min(đen,trắng) luôn đạt được.
  • Dãy con tăng dài nhất (icpc22mbi): (Master) Với mỗi truy vấn (M,K), tìm dãy con dài nhất của M phần tử đầu có LIS không quá K. Đáp án là ∑imin(λi,K) theo định lý Greene trên bảng RSK của tiền tố, dựng dần offline và cắt cụt số hàng theo N.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0