Trên một lưới 4 × 4, các lộ trình từ góc dưới trái đến góc trên phải chỉ bước lên và sang phải là 8!/(4!·4!) = 70 và bàn làm việc in thành liên kết thứ hai. Phần lớn thêm quy tắc «không bao giờ vượt lên trên đường chéo» và khi đó phép đếm là 8!/(4!·5!) = 14. Hai công thức khác nhau đúng thừa số n + 1 ở mẫu số, và đó là toàn bộ hiệu chỉnh Catalan.
56 đường bất hợp lệ không nằm rải rác: bằng lập luận phản chiếu, vượt đường chéo ghép chúng một đối một với các lộ trình tới một đầu mút đã dịch, và những lộ trình đó là 8!/(3!·5!) = 56. Nên 70 − 56 = 14 và hai màn hình đồng thuận. Cùng dãy 1, 2, 5, 14, 42 đếm số cách đặt ngoặc cho một dãy thừa số, các phép tam giác phân một đa giác lồi và các dãy ngoặc hợp lệ: liên kết thứ ba là C₅ = 10!/(5!·6!) = 42, số kế tiếp, cũng là số phép tam giác phân của một thất giác.
Đáp án
14
Cách đọc
C₄ dưới dạng 8!/(4!·5!) trong bàn làm việc. Liên kết thứ hai là phép đếm không ràng buộc 8!/(4!·4!) = 70 và liên kết thứ ba là số Catalan kế tiếp, 42.
Nguồn
The Catalan numbers Cₙ = (2n)!/(n!(n+1)!) count monotone lattice paths that stay on one side of the diagonal; Euler used the sequence for polygon triangulations in 1751, the Chinese mathematician Ming'an derived the formula in the 1730s, and Eugène Catalan gave the name in 1838
Giải trong máy tính
Các liên kết này mở đúng máy tính với các con số của bài toán đã nhập sẵn. Dòng bên trên là những gì màn hình phải hiện — hãy tự kiểm tra.