Tổng quan
Hãy đếm số hình dạng của cây tìm kiếm nhị phân, số cách lồng ngoặc hợp lệ, hay số cách tam giác hóa đa giác, và cùng những con số ấy cứ xuất hiện: 1, 1, 2, 5, 14, 42, 132.
Cách giải 1, 1, 2, 5, 14, …? từng bước
- Hãy chọn gốc của cây. Nếu bên trái có k khóa thì bên phải có n−1−k khóa.
- Điều đó cho hệ thức Cₙ = Σ Cₖ · Cₙ₋₁₋ₖ trên mọi cách chia — một tích chập, không phải một phép hiệu đơn giản.
- Tính tổng cho dạng đóng Cₙ = C(2n, n)/(n + 1), nên C₅ = 252/6 = 42.
Mấu chốt
Mọi đối tượng Catalan thực ra là cùng một đối tượng: một xâu ngoặc đúng CHÍNH LÀ một hình dạng cây CHÍNH LÀ một đường đi trên lưới không vượt đường chéo. Khi bạn thấy một song ánh, cả họ đối tượng co lại thành một con số duy nhất.
Biến thể & liên hệ
- Cₙ cũng đếm số cách đặt ngoặc đầy đủ cho phép nhân n + 1 nhân tử — lý do nó xuất hiện trong quy hoạch động chuỗi ma trận.
- Tỉ số Cₙ₊₁/Cₙ tiến tới 4, nên các số Catalan tăng xấp xỉ 4ⁿ/n^1,5.
Câu hỏi thường gặp
Vì sao phép hiệu không hé lộ quy luật?
Vì dãy được tạo bằng phép nhân và tích chập, không phải phép cộng. Tỉ số (hoặc dạng đóng) mới phơi bày nó; phép hiệu thì không bao giờ.