Số Catalan trong tổ hợp

Số Catalan và Ứng Dụng Đếm Số Cách Chia Đa Giác Thành Tam Giác

1. Giới thiệu về số Catalan

1.1. Định nghĩa

Số Catalan thứ $n$, ký hiệu $C_n$, là một dãy số nguyên xuất hiện trong nhiều bài toán đếm khác nhau trong toán học tổ hợp. Công thức tổng quát của số Catalan thứ $n$ là:

$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$

trong đó $n \geq 0$ là một số nguyên.

1.2. Một vài giá trị đầu tiên

Dưới đây là một vài giá trị đầu tiên của dãy số Catalan:

$n$	0	1	2	3	4	5	6	7	8	9	10
$C_n$	1	1	2	5	14	42	132	429	1430	4862	16796

2. Ứng dụng của số Catalan trong bài toán chia đa giác thành tam giác

2.1. Phát biểu bài toán

Cho một đa giác lồi có $n+2$ cạnh (gọi là đa giác $(n+2)$-giác). Hãy tính số cách chia đa giác này thành các tam giác bằng cách vẽ các đường chéo không giao nhau bên trong đa giác.

2.2. Ví dụ minh họa

• Với $n=1$, ta có tam giác (3 cạnh). Chỉ có 1 cách chia (bản thân nó là một tam giác).
• Với $n=2$, ta có tứ giác (4 cạnh). Có 2 cách chia thành 2 tam giác bằng cách vẽ một đường chéo.
• Với $n=3$, ta có ngũ giác (5 cạnh). Có 5 cách chia thành 3 tam giác bằng cách vẽ hai đường chéo.
• Với $n=4$, ta có lục giác (6 cạnh). Có 14 cách chia thành 4 tam giác bằng cách vẽ ba đường chéo.

2.3. Giải quyết bài toán bằng số Catalan

Số cách chia một đa giác lồi $(n+2)$-giác thành các tam giác bằng cách vẽ các đường chéo không giao nhau bên trong đa giác chính là số Catalan $C_n$.

Chứng minh (Sử dụng phương pháp quy nạp)

• Trường hợp cơ sở: Với $n=1$, đa giác là tam giác, có $C_1 = 1$ cách chia. Mệnh đề đúng.

• Giả thiết quy nạp: Giả sử mệnh đề đúng đến $n=k$, tức là số cách chia đa giác lồi $(k+2)$-giác thành các tam giác là $C_k$.

• Bước quy nạp: Xét đa giác lồi $(k+3)$-giác, ký hiệu là $A_0A_1...A_{k+2}$. Ta chọn một cạnh cố định, ví dụ $A_0A_{k+2}$. Cạnh này sẽ thuộc một tam giác duy nhất trong cách chia, giả sử tam giác đó là $A_iA_0A_{k+2}$ với $1 \leq i \leq k+1$. Khi đó, tam giác $A_iA_0A_{k+2}$ chia đa giác $(k+3)$-giác thành hai đa giác nhỏ hơn:

  • Đa giác $A_0A_1...A_i$ có $i+1$ cạnh (là một đa giác $(i-1)+2$-giác). Số cách chia đa giác này là $C_{i-1}$.
  • Đa giác $A_iA_{i+1}...A_{k+2}$ có $(k+3) - i$ cạnh (là một đa giác $(k+1-i)+2$-giác). Số cách chia đa giác này là $C_{k+1-i}$.

  Vậy, với mỗi giá trị $i$ từ 1 đến $k+1$, số cách chia đa giác $(k+3)$-giác thông qua tam giác $A_iA_0A_{k+2}$ là $C_{i-1}C_{k+1-i}$. Tổng số cách chia đa giác $(k+3)$-giác là:

  $C_{k+1} = \sum_{i=1}^{k+1} C_{i-1}C_{k+1-i} = \sum_{i=0}^{k} C_iC_{k-i}$

  Công thức trên là công thức truy hồi của số Catalan. Có thể chứng minh (bằng đại số) rằng công thức truy hồi này tương đương với công thức tổng quát. Như vậy, mệnh đề đúng với $n=k+1$.

  Theo nguyên lý quy nạp toán học, mệnh đề đúng với mọi $n \geq 1$.

2.4. Kết luận

Số cách chia một đa giác lồi $(n+2)$-giác thành các tam giác bằng cách vẽ các đường chéo không giao nhau bên trong đa giác là số Catalan $C_n = \frac{1}{n+1} \binom{2n}{n}$.

3. Ví dụ áp dụng

Ví dụ 1: Tính số cách chia một thất giác (7 cạnh) thành các tam giác.

Giải:

Thất giác là đa giác $(5+2)$-giác, vậy $n=5$. Số cách chia là $C_5 = \frac{1}{5+1}\binom{2 \cdot 5}{5} = \frac{1}{6} \binom{10}{5} = \frac{1}{6} \cdot \frac{10!}{5!5!} = \frac{1}{6} \cdot 252 = 42$.

Ví dụ 2: Một lớp học có 6 học sinh tham gia một buổi tiệc. Các em bắt tay nhau một cách ngẫu nhiên. Tính số cách bắt tay sao cho không có cặp tay nào giao nhau (các cánh tay không cắt nhau).

Giải:

Bài toán này có thể được mô hình hóa thành bài toán chia đa giác. Ta coi 6 học sinh là 6 đỉnh của một lục giác. Mỗi cái bắt tay tương ứng với một đoạn thẳng nối hai đỉnh. Yêu cầu không có cặp tay nào giao nhau tương ứng với các đường chéo không giao nhau. Do đó, bài toán trở thành tìm số cách chia một lục giác thành các tam giác, tức là $C_{6-2} = C_4 = 14$.

4. Bài tập tự luyện

1. Tính số cách chia một bát giác (8 cạnh) thành các tam giác.
2. Tính số cách chia một thập giác (10 cạnh) thành các tam giác.
3. Một dãy núi có 10 đỉnh. Tính số cách đi từ đỉnh đầu đến đỉnh cuối sao cho không bao giờ xuống thấp hơn điểm xuất phát. (Gợi ý: Liên hệ với số Catalan).
4. Có bao nhiêu cách đặt dấu ngoặc đúng cho một biểu thức gồm $n$ cặp dấu ngoặc?
5. Chứng minh công thức truy hồi của số Catalan: $C_{n+1} = \sum_{i=0}^{n} C_iC_{n-i}$.

5. Tài liệu tham khảo

• "Concrete Mathematics" by Graham, Knuth, and Patashnik
• "Proofs That Really Count: The Art of Combinatorial Argument" by Arthur T. Benjamin and Jennifer J. Quinn

Hy vọng tài liệu này sẽ giúp các bạn hiểu rõ hơn về số Catalan và ứng dụng của nó trong bài toán chia đa giác thành tam giác. Chúc các bạn học tốt!