Các số Catalan xuất hiện ở đâu?
-Số psp với một số cặp dấu ngoặc nhất định
-Số cây nhị phân với số lá cho trước
-Số đường dẫn từ góc dưới bên trái lên góc trên bên phải trong hình vuông thứ n * n không chạm vào đường chéo
-Số lần chia n-giác thành tam giác
Cách đếm?1) Công thức cho số Catalan thứ n:
2)
•Hãy có một PSS dài 2n
•Rõ ràng là nó bắt đầu bằng một dấu ngoặc mở
•Vì vậy, giả sử P = (A)B, trong đó A và B – cả psp (hơn nữa, A và B có thể để trống)
•Nếu độ dài của A = 2k thì dãy A có thể được lập theo Ck cách
•Sau đó, độ dài của B = 2(n – k - 1) và B có thể được tạo thành theo các cách Cn-k-1
•Chúng ta thấy công thức cho dp: Cn = sum(Ck * Cn-k-1) cho mọi k <
Vật liệu được sử dụng: