কাতালান সংখ্যা হল সংখ্যার একটি ক্রম। কাতালান সংখ্যাগুলি প্রাকৃতিক সংখ্যাগুলির একটি ক্রম গঠন করে যা বিভিন্ন গণনা সমস্যায় ঘটে, প্রায়শই পুনরাবৃত্তিমূলকভাবে সংজ্ঞায়িত বস্তু জড়িত থাকে।
-
Cn 2n দৈর্ঘ্যের Dyck শব্দের সংখ্যা। একটি Dyck শব্দ হল n X এবং n Y এর সমন্বয়ে গঠিত একটি স্ট্রিং যাতে স্ট্রিংয়ের কোনো প্রাথমিক সেগমেন্টে X-এর চেয়ে বেশি Y নেই। উদাহরণস্বরূপ, নিম্নলিখিত দৈর্ঘ্য 6
এর Dyck শব্দ
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
