Một đa giác lồi n cạnh có thể chia thành tam giác bằng các đường chéo không cắt nhau theo đúng C(n−2) cách, trong đó C là số Catalan: tứ giác có 2 cách, ngũ giác 5 cách, lục giác 14 cách, thất giác 42 cách, bát giác 132 cách. Cách chia nào cũng dùng đúng n − 3 đường chéo và cho đúng n − 2 tam giác. Leonhard Euler đếm ra dãy số này năm 1751, và nó xuất hiện lại trong hàng trăm bài toán đếm khác.
Những con số đầu tiên
| Đa giác | Số cạnh n | Số đường chéo dùng | Số tam giác | Số cách chia |
|---|---|---|---|---|
| Tam giác | 3 | 0 | 1 | 1 |
| Tứ giác | 4 | 1 | 2 | 2 |
| Ngũ giác | 5 | 2 | 3 | 5 |
| Lục giác | 6 | 3 | 4 | 14 |
| Thất giác | 7 | 4 | 5 | 42 |
| Bát giác | 8 | 5 | 6 | 132 |
| Cửu giác | 9 | 6 | 7 | 429 |
| Thập giác | 10 | 7 | 8 | 1.430 |
Cột cuối là dãy Catalan 1, 1, 2, 5, 14, 42, 132, 429, 1.430, 4.862… lệch đi hai bậc. Số tam giác bằng n − 2 thì khớp với điều quen thuộc: tổng các góc trong của đa giác n cạnh là (n − 2) × 180 độ, đúng bằng tổng góc của n − 2 tam giác.
Tự đếm bằng tay: ngũ giác và lục giác
Ngũ giác: 5 cách
Đặt tên các đỉnh A, B, C, D, E theo vòng. Mỗi cách chia cần 2 đường chéo không cắt nhau, và hai đường đó phải chung một đỉnh. Có 5 đỉnh, mỗi đỉnh cho một "chiếc quạt" gồm hai đường chéo xuất phát từ nó: từ A là AC và AD, từ B là BD và BE, cứ thế. Năm đỉnh, năm cách. Hai đường chéo không chung đỉnh trong ngũ giác thì luôn cắt nhau, nên không còn cách nào khác.
Lục giác: 14 cách, chia thành ba kiểu
- Kiểu quạt (6 cách): ba đường chéo cùng xuất phát từ một đỉnh. Sáu đỉnh, sáu cách.
- Kiểu chữ Z (6 cách): ba đường chéo nối thành đường gấp khúc, ví dụ AC, CF, FD. Có 3 hướng đặt chữ Z, mỗi hướng có bản thuận và bản soi gương.
- Kiểu tam giác giữa (2 cách): ba đường chéo tạo thành một tam giác ở giữa, ACE hoặc BDF.
6 + 6 + 2 = 14. Chia theo kiểu như vậy giúp đếm không sót, không trùng, và là cách nên dạy trẻ khi tập đếm có hệ thống.
Công thức truy hồi: cố định một cạnh
Đếm tay tới thất giác thì đã mỏi. Mẹo giúp đếm mọi đa giác: chọn một cạnh cố định làm "đáy". Trong mọi cách chia, cạnh đáy thuộc đúng một tam giác, và đỉnh thứ ba của tam giác đó là một trong các đỉnh còn lại. Tam giác này tách đa giác thành hai đa giác nhỏ hơn ở hai bên, mỗi bên lại chia tiếp độc lập.
Gọi T(m) là số cách chia đa giác m đỉnh, quy ước T(2) = 1 (một cạnh trơ, không cần chia). Với thất giác đỉnh 1 tới 7, đáy là cạnh 1–7, đỉnh thứ ba là k:
| Đỉnh thứ ba k | Bên trái (đỉnh 1…k) | Bên phải (đỉnh k…7) | Số cách |
|---|---|---|---|
| 2 | cạnh trơ, 1 cách | lục giác, 14 cách | 14 |
| 3 | tam giác, 1 cách | ngũ giác, 5 cách | 5 |
| 4 | tứ giác, 2 cách | tứ giác, 2 cách | 4 |
| 5 | ngũ giác, 5 cách | tam giác, 1 cách | 5 |
| 6 | lục giác, 14 cách | cạnh trơ, 1 cách | 14 |
Cộng lại 14 + 5 + 4 + 5 + 14 = 42. Đây chính là công thức truy hồi của số Catalan: mỗi số bằng tổng các tích của những số trước nó, ghép đối xứng từ hai đầu. Có cả công thức đóng: C(k) = (2k)! / ((k+1)! × k!), ví dụ C(5) = 10! / (6! × 5!) = 3.628.800 / (720 × 120) = 42.
Lịch sử: Euler, Segner, rồi Catalan
Năm 1751, trong một lá thư gửi Christian Goldbach, Euler nêu bài toán đếm cách chia đa giác thành tam giác và đưa ra các giá trị đầu cùng một công thức, nhưng chưa có chứng minh đầy đủ. Năm 1758, Johann Andreas von Segner công bố công thức truy hồi như cách cố định cạnh đáy ở trên. Mãi tới năm 1838, nhà toán học Eugène Charles Catalan (sinh ở Bruges, làm việc ở Pháp rồi Bỉ) nghiên cứu dãy số này qua bài toán đặt dấu ngoặc, và tên ông gắn với dãy số từ đó, dù ông không phải người phát hiện đầu tiên. Người ta cũng biết nhà toán học Mông Cổ Minh An Đồ (Minggatu) đã gặp dãy này trong các khai triển lượng giác từ khoảng thập niên 1730, sớm hơn Euler.
Số Catalan ở chỗ khác: cùng một con số, nhiều bài toán
Dãy Catalan nổi tiếng vì cùng một con số đếm nhiều thứ trông chẳng liên quan. Với ngũ giác (5 cách), có đúng 5 cách cho mỗi việc sau:
- Đặt dấu ngoặc cho tích bốn số a·b·c·d: ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)). Mỗi cách tương ứng với một cách chia ngũ giác: đánh nhãn bốn cạnh bằng a, b, c, d, cạnh thứ năm là kết quả, mỗi đường chéo là một tích trung gian.
- Xếp 3 cặp ngoặc đóng mở hợp lệ: ()()(), ()(()), (())(), (()()), ((())).
- Đường đi trên lưới: đi từ góc dưới trái tới góc trên phải của lưới 3 × 3, mỗi bước sang phải hoặc lên trên, không vượt lên trên đường chéo.
- Bắt tay quanh bàn tròn: 6 người ngồi quanh bàn bắt tay từng đôi một lúc, không cánh tay nào bắt chéo qua cánh tay khác.
Nhà toán học Richard Stanley đã gom hơn 200 cách hiểu khác nhau của số Catalan vào cuốn sách Catalan Numbers (2015).
Chia tam giác để làm gì: bài toán phòng tranh
Ngoài chuyện đếm, chia đa giác thành tam giác là công cụ thật sự hữu ích. Một ví dụ đẹp là bài toán phòng tranh, do Victor Klee đặt ra năm 1973: một phòng trưng bày có mặt bằng là đa giác n cạnh (có thể lõm, nhiều ngóc ngách), cần ít nhất bao nhiêu người bảo vệ đứng cố định để mọi điểm trong phòng đều được ít nhất một người nhìn thấy?
Năm 1975, Václav Chvátal chứng minh: chỉ cần n/3 người, làm tròn xuống, và có những mặt bằng hình răng lược bắt buộc phải dùng đủ chừng ấy. Năm 1978, Steve Fisk đưa ra chứng minh ngắn gọn dùng đúng việc chia tam giác:
- Chia mặt bằng thành tam giác bằng các đường chéo nằm trong phòng. Mọi đa giác, kể cả lõm, đều chia được như vậy.
- Tô ba màu cho các đỉnh sao cho mỗi tam giác có đủ ba màu. Việc này luôn làm được nhờ cấu trúc "cây" của cách chia.
- Màu nào ít đỉnh nhất thì có không quá n/3 đỉnh. Đặt bảo vệ ở các đỉnh màu đó. Tam giác nào cũng có một đỉnh màu ấy, và người đứng ở đỉnh nhìn thấy trọn tam giác.
Với phòng 12 cạnh, 4 người là đủ; với phòng 20 cạnh, 6 người. Trong đồ hoạ máy tính, mô hình 3D được lưới hoá thành tam giác cũng vì tam giác luôn phẳng và dễ tính diện tích, hướng sáng.
Góc nhìn hôm nay: đo diện tích thửa đất lạ bằng tam giác
Người làm vườn, làm xây dựng dùng nguyên lý chia tam giác mỗi ngày mà không gọi tên. Thửa đất năm cạnh không có công thức diện tích riêng, nhưng chọn một góc, kéo dây tới hai góc không kề nó là được ba tam giác. Đo ba cạnh mỗi tam giác, tính diện tích bằng công thức Heron (căn bậc hai của p(p−a)(p−b)(p−c), với p là nửa chu vi), cộng lại. Chọn cách chia nào trong 5 cách cũng ra cùng tổng; nếu ra khác nhau nhiều, đó là dấu hiệu đo sai.
Người muốn đọc thêm có thể tìm cuốn Catalan Numbers của Richard Stanley, hoặc tra mã A000108 trên OEIS để xem danh sách các bài toán cùng ra dãy số này.
Câu hỏi thường gặp
Có bao nhiêu cách chia lục giác thành tam giác?
Lục giác lồi có 14 cách chia thành 4 tam giác bằng 3 đường chéo không cắt nhau. Gồm 6 cách hình quạt (ba đường chéo từ một đỉnh), 6 cách hình chữ Z và 2 cách có tam giác ở giữa. Con số 14 là số Catalan thứ tư.
Số Catalan là gì?
Số Catalan là dãy 1, 1, 2, 5, 14, 42, 132, 429… tính bằng công thức (2n)! chia cho (n+1)! nhân n!. Dãy này đếm số cách chia đa giác thành tam giác, số cách đặt dấu ngoặc, số dãy ngoặc hợp lệ và hàng trăm cấu trúc tổ hợp khác.
Đa giác n cạnh chia được thành bao nhiêu tam giác?
Chia bằng các đường chéo không cắt nhau, đa giác n cạnh luôn cho đúng n − 2 tam giác và dùng đúng n − 3 đường chéo, dù chia theo cách nào. Số cách chia khác nhau với đa giác lồi là số Catalan thứ n − 2.
Ai phát hiện ra số Catalan?
Euler đếm số cách chia đa giác thành tam giác trong thư gửi Goldbach năm 1751, Segner đưa ra công thức truy hồi năm 1758. Minggatu, nhà toán học người Mông Cổ làm việc dưới triều Thanh, đã gặp dãy số này từ thập niên 1730. Tên Catalan gắn với dãy số sau công trình của Eugène Catalan năm 1838.
Bài toán phòng tranh là gì?
Đó là câu hỏi: một phòng hình đa giác n cạnh cần ít nhất bao nhiêu người bảo vệ để nhìn thấy mọi chỗ. Chvátal chứng minh năm 1975 rằng n/3 (làm tròn xuống) là đủ và đôi khi cần đủ. Chứng minh của Fisk năm 1978 dùng chia tam giác và tô ba màu đỉnh.