ক্যাটালান সংখ্যাগুলো একটি সংখ্যা সিকোয়েন্স। ক্যাটালান সংখ্যাগুলো প্রাকৃতিক সংখ্যার একটি সিকোয়েন্স তৈরি করে যা বিভিন্ন গণনা সমস্যায় দেখা যায়, প্রায়শই রিকার্সিভলি ডিফাইনড অবজেক্ট জড়িত।
Cn ২n দৈর্ঘ্যের ডাইক ওয়ার্ডের সংখ্যা। ডাইক ওয়ার্ড হলো n개의 X এবং n개의 Y নিয়ে তৈরি স্ট্রিং যেখানে স্ট্রিংয়ের কোনো প্রাথমিক সেগমেন্টে X-র চেয়ে Y বেশি থাকে না। উদাহরণস্বরূপ, দৈর্ঘ্য ৬-এর ডাইক ওয়ার্ডগুলো:
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 পাতাযুক্ত ফুল বাইনারি ট্রির সংখ্যা।
নমুনা
ইনপুট - ৬
আউটপুট - 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
