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.
Biểu đồ Young (Young diagram) của một phân hoạch của số là hình gồm hàng ô vuông căn trái, hàng có ô. Bảng Young chuẩn (standard Young tableau, SYT) là cách điền các số 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 , tính trong 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 hàng (hoặc cột) đầu cho kích thước lớn nhất của hợp dãy con tăng (hoặc không tăng). Chèn một phần tử tốn với 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 ", hay "dãy con dài nhất có LIS không quá " đều quy về hai công cụ này.
Ý tưởng / Trực giác
Móc của một ô. Với ô ở hàng , cột , móc gồm chính ô đó, các ô bên phải nó trong cùng hàng (cánh tay, ô nếu đánh số cột từ ) và các ô bên dưới nó trong cùng cột (cái chân, ô, với là độ cao cột ). Độ dài móc
Công thức móc (Frame, Robinson, Thrall 1954):
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 cách điền, ràng buộc ở ô là "số tại nhỏ nhất trong móc của nó", xác suất ; 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 đúng bằng , mà số trong SYT luôn nằm ở một góc, nên (luật rẽ nhánh). Biểu thức 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 có mỗi hàng tăng ngặt. Để chèn :
- Ở hàng , tìm phần tử trái nhất . Nếu không có, đặt vào cuối hàng và dừng.
- Nếu có phần tử như vậy, thay bằng ("đẩy" ra), rồi chèn vào hàng 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 chính là mảng d của thuật toán LIS quen thuộc (d[k] = phần tử cuối nhỏ nhất của dãy con tăng độ dài ), nên 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 (quy tắc như trên). Khi đó với mọi :
- = kích thước lớn nhất của hợp dãy con tăng ngặt rời nhau;
- = kích thước lớn nhất của hợp dãy con không tăng rời nhau.
Với 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 (bảng ghi), thì hoán vị cặp cùng hình dạng là một song ánh. Hệ quả: số hoán vị của phần tử có bảng hình dạng là , và . Muốn đếm số hoán vị có LIS bằng , ta cộng trên các có .
Ví dụ chạy tay
Đếm bảng chuẩn hình . Độ dài móc từng ô:
5 3 1
3 1
1
Ví dụ ô góc trái trên: cánh tay ô, chân ô, cộng chính nó: . Tích các móc là , nên
Kiểm tra bằng luật rẽ nhánh: có ba góc, bỏ đi được , , , với lần lượt ; tổng .
Chèn RSK dãy (có phần tử lặp, quy tắc "trái nhất "):
| chèn | thao tác | bảng sau bước |
|---|---|---|
| 3 | hàng 1 trống, đặt cuối | [3] |
| 1 | hàng 1: , thay bằng , đẩy xuống hàng 2 | [1] / [3] |
| 4 | hàng 1: không có phần tử , đặt cuối | [1 4] / [3] |
| 1 | hàng 1: , thay, đẩy ; hàng 2: , thay, đẩy ; 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: , thay, đẩy ; hàng 2: không có phần tử , đặt cuối | [1 2 5] / [1 4] / [3] |
Bảng cuối:
1 2 5
1 4
3
Hình dạng . Đọc theo Greene:
- : LIS dài (ví dụ ). Lưu ý hàng của bảng không phải một dãy con của dãy gốc ( đứng sau ).
- : hai dãy con tăng ngặt rời nhau phủ được phần tử, ví dụ và .
- : dãy con không tăng dài nhất dài (ví dụ ).
- : hai dãy con không tăng phủ được phần tử, ví dụ và . Nói cách khác, dãy con dài nhất có LIS có 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 (với ) và .
Cài đặt
Chương trình đọc và dãy , dựng bảng RSK, in các hàng, in với mỗi kích thước lớn nhất của hợp 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 ).
#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';
}
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 . 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ó ô | ||
| Chèn một phần tử vào bảng RSK có hàng | ||
| Dựng toàn bộ bảng RSK của dãy độ dài | , xấu nhất | |
| Chỉ giữ hàng đầu |
Vì sao công thức móc là ? Mỗi ô tính móc trong nhờ mảng độ cao cột; giai thừa ; một lần nghịch đảo modulo .
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 hàng nên tổng là lần tìm kiếm nhị phân. Mẹo cắt cụt: 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 không bao giờ quay lại), nên nếu câu hỏi chỉ cần 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 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_boundcho hàng tăng ngặt (LIS tăng ngặt, cột ứng với dãy không tăng),upper_boundcho 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 trong ví dụ không phải dãy con của . 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ừ , . Quên ở 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 (phải ra ) và hình (phải ra ).
- Chia modulo khi : công thức chia cho tích các móc, mỗi móc . Nếu modulo nhỏ hơn hoặc bằng (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 và các móc rồi trừ số mũ.
- Quên rằng 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 dùng công thức móc-nội dung khác: (vớ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 hàng và RSK đầy đủ thành . 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 là ; duyệt phân hoạch của nhỏ là đủ. Số hoán vị tự nghịch đảo (involution) có hình là .
- 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: , 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 cho đúng số Catalan .
- 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 " tương đương "phân hoạch được thành 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 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 luôn đạt được.
- Dãy con tăng dài nhất (icpc22mbi): (Master) Với mỗi truy vấn , tìm dãy con dài nhất của phần tử đầu có LIS không quá . Đáp án là 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 .
Bình luận