Bốn bước lên và bốn bước ngang không vượt đường chéo: 14 trong 70 đường

Hệ số nhị thức trung tâm đếm mọi lộ trình; công thức Catalan đếm những lộ trình hợp lệ.

Thống kê và dữ liệu · Mức độ: Kết quả kinh điển · Cập nhật ngày 2026-11-10

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.

Đây là một trang công cụ độc lập của bên thứ ba. Trang không liên kết, được tài trợ hay ủy quyền bởi Casio, Texas Instruments hoặc các nhà phân phối của họ. Tên model và sản phẩm là nhãn hiệu của các chủ sở hữu tương ứng và chỉ được dùng ở đây để nhận diện thiết bị.

Các chuỗi phím trong những hướng dẫn này được viết dựa trên dữ liệu bố cục riêng của trang — chính là dữ liệu mà máy tính trực tuyến sử dụng — cùng với thông tin sản phẩm công khai. Thông số kỹ thuật và cấu hình theo khu vực được kiểm chứng trên thiết bị thật và tài liệu mới nhất của nhà sản xuất.