Catalan Numbers คือ ลำดับตัวเลขที่พบในปัญหาการนับหลายอย่าง มักเกี่ยวกับโครงสร้าง Recursive
- C_n = จำนวน Dyck Words ความยาว 2n (สตริง n X และ n Y ที่ Prefix ใดๆ มี X มากกว่าหรือเท่า Y) เช่น n=3: XXXYYY, XYXXYY, XYXYXY, XXYYXY, XXYXYY
- ถ้า X = '(' Y = ')' C_n = จำนวนนิพจน์วงเล็บถูกต้อง n คู่: ((())), ()(()), ()()(), (())(), (()())
- C_n = จำนวนวิธี Parenthesize n+1 ตัวประกอบ (n=3: ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)))
- C_n = จำนวน Full Binary Trees ที่มี n+1 ใบ
ตัวอย่าง
Input - 6 Output - 1 1 2 5 14 42
Catalan Numbers 10 ตัวแรก (n=0..9): 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862
ตัวอย่าง
#include <iostream>
using namespace std;
long int catalan(int n) {
if (n <= 1) return 1;
long int result = 0;
for (int i = 0; i < n; i++) {
result += catalan(i) * catalan(n - i - 1);
}
return result;
}
int main() {
for (int i = 0; i < 6; i++) cout << catalan(i) << " ";
return 0;
}ผลลัพธ์
1 1 2 5 14 42
