หมายเลขคาตาลันเป็นลำดับของตัวเลข ตัวเลขคาตาลันเป็นลำดับของจำนวนธรรมชาติที่เกิดขึ้นในปัญหาการนับต่างๆ ซึ่งมักเกี่ยวข้องกับอ็อบเจกต์ที่กำหนดแบบเรียกซ้ำ
-
Cn คือจำนวนคำ Dyck ที่มีความยาว 2n คำ Dyck คือสตริงที่ประกอบด้วย n X และ n Y โดยที่ส่วนเริ่มต้นของสตริงไม่มี Y's มากกว่า X ตัวอย่างเช่น ต่อไปนี้เป็นคำ Dyck ที่มีความยาว 6
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
-
ตีความสัญลักษณ์ X ใหม่เป็นวงเล็บเปิด และ Y เป็นวงเล็บปิด Cn นับจำนวนนิพจน์ที่มีวงเล็บ n คู่ที่จับคู่อย่างถูกต้อง
((())) ()(()) ()()() (())() (()())
-
Cn คือจำนวนวิธีที่แตกต่างกัน n + 1 ตัวประกอบสามารถอยู่ในวงเล็บได้อย่างสมบูรณ์ (หรือจำนวนวิธีในการเชื่อมโยงแอปพลิเคชัน n ตัวของตัวดำเนินการไบนารี) ตัวอย่างเช่น สำหรับ n =3 เรามีวงเล็บที่แตกต่างกันห้าตัวต่อไปนี้ของปัจจัยสี่ตัว:
((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
-
แอปพลิเคชันที่ต่อเนื่องกันของตัวดำเนินการไบนารีสามารถแสดงในรูปของต้นไม้ไบนารีแบบเต็ม (ไบนารีทรีที่รูทจะเต็มถ้าทุกจุดยอดมีลูกสองคนหรือไม่มีลูก) ตามด้วย Cn คือจำนวนต้นไม้ไบนารีเต็มที่มี n + 1 ใบ:
ตัวอย่าง
ป้อนข้อมูล - 6
ผลผลิต - 1 1 2 5 14 42
คำอธิบาย
ตัวเลขคาตาลันแรกสำหรับ n =0, 1, 2, 3,4,5,6,7,8,9,10, ... คือ
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
