ক্যাটালান সংখ্যা#

ক্যাটালান সংখ্যা হলো একটি সংখ্যা ক্রম, যা বিভিন্ন কম্বিনেটরিক্স সমস্যায় কাজে আসে, বিশেষ করে যেসব সমস্যায় রিকার্সিভভাবে সংজ্ঞায়িত অবজেক্ট জড়িত থাকে।

এই ক্রমটি বেলজিয়ান গণিতবিদ Catalan-এর নামে নামকরণ করা হয়েছে, যিনি ১৯শ শতকে জীবিত ছিলেন। (প্রকৃতপক্ষে ক্যাটালানের এক শতক আগে অয়লারের কাছে এটি পরিচিত ছিল)।

প্রথম কয়েকটি ক্যাটালান সংখ্যা $C_n$ (শূন্য থেকে শুরু করে):

$1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$

কিছু কম্বিনেটরিক্স সমস্যায় প্রয়োগ#

ক্যাটালান সংখ্যা $C_n$ হলো নিম্নলিখিত সমস্যাগুলোর সমাধান:

  • $n$টি ওপেনিং এবং $n$টি ক্লোজিং ব্র্যাকেট নিয়ে গঠিত সঠিক ব্র্যাকেট সিকোয়েন্সের সংখ্যা।
  • $n + 1$টি লিফ সহ রুটেড ফুল বাইনারি ট্রি-এর সংখ্যা (ভার্টেক্সগুলো নম্বরবিহীন)। একটি রুটেড বাইনারি ট্রি ফুল হয় যদি প্রতিটি ভার্টেক্সের হয় দুটি চাইল্ড থাকে অথবা কোনো চাইল্ড না থাকে।
  • $n + 1$টি ফ্যাক্টরকে সম্পূর্ণরূপে বন্ধনীবদ্ধ করার উপায়ের সংখ্যা।
  • $n + 2$ বাহুবিশিষ্ট একটি উত্তল বহুভুজের ত্রিভুজায়নের সংখ্যা (অর্থাৎ কর্ণ ব্যবহার করে বহুভুজটিকে অবিচ্ছিন্ন ত্রিভুজে বিভক্ত করার উপায়ের সংখ্যা)।
  • একটি বৃত্তের $2n$টি বিন্দুকে সংযুক্ত করে $n$টি অবিচ্ছিন্ন জ্যা তৈরি করার উপায়ের সংখ্যা।
  • $n$টি ইন্টারনাল নোড সহ নন-আইসোমর্ফিক ফুল বাইনারি ট্রি-এর সংখ্যা (অর্থাৎ এমন নোড যাদের অন্তত একটি চাইল্ড আছে)।
  • $n \times n$ আকারের একটি বর্গাকার ল্যাটিসে $(0, 0)$ বিন্দু থেকে $(n, n)$ বিন্দু পর্যন্ত মনোটনিক ল্যাটিস পাথের সংখ্যা, যা মূল কর্ণের (অর্থাৎ $(0, 0)$ এবং $(n, n)$ সংযোগকারী) উপরে যায় না।
  • দৈর্ঘ্য $n$-এর পারমুটেশনের সংখ্যা যেগুলো স্ট্যাক সর্ট করা যায় (অর্থাৎ দেখানো যায় যে পুনর্বিন্যাসটি স্ট্যাক সর্টেড হয় যদি এবং কেবলমাত্র যদি এমন কোনো ইনডেক্স $i < j < k$ না থাকে যেখানে $a_k < a_i < a_j$)।
  • $n$ উপাদানের একটি সেটের নন-ক্রসিং পার্টিশন-এর সংখ্যা।
  • $n$টি আয়তক্ষেত্র ব্যবহার করে $1 \ldots n$ মই ঢাকার উপায়ের সংখ্যা (মইটিতে $n$টি কলাম আছে, যেখানে $i$-তম কলামের উচ্চতা $i$)।

গণনা#

ক্যাটালান সংখ্যার দুটি সূত্র আছে: রিকার্সিভ এবং বিশ্লেষণাত্মক। যেহেতু আমরা বিশ্বাস করি যে উপরে উল্লেখিত সব সমস্যা সমতুল্য (একই সমাধান আছে), তাই নিচের সূত্রগুলোর প্রমাণের জন্য আমরা এমন সমস্যা বেছে নেব যেটি সবচেয়ে সহজ।

রিকার্সিভ সূত্র#

$$C_0 = C_1 = 1$$$$C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 2$$

রিকারেন্স সূত্রটি সঠিক ব্র্যাকেট সিকোয়েন্সের সমস্যা থেকে সহজেই বের করা যায়।

সবচেয়ে বাঁদিকের ওপেনিং বন্ধনী $l$ একটি নির্দিষ্ট ক্লোজিং ব্র্যাকেট $r$-এর সাথে মিলে, যা সিকোয়েন্সটিকে ২টি অংশে ভাগ করে এবং প্রতিটি অংশও একটি সঠিক ব্র্যাকেট সিকোয়েন্স হওয়া উচিত। তাই সূত্রটিও ২টি অংশে বিভক্ত হয়। যদি আমরা $k = {r - l - 1}$ বলি, তাহলে একটি নির্দিষ্ট $r$-এর জন্য ঠিক $C_k C_{n-1-k}$টি এমন ব্র্যাকেট সিকোয়েন্স থাকবে। সব গ্রহণযোগ্য $k$-এর উপর যোগফল করলে আমরা $C_n$-এর রিকারেন্স সম্পর্ক পাই।

আপনি এটি এভাবেও চিন্তা করতে পারেন। সংজ্ঞা অনুসারে, $C_n$ সঠিক ব্র্যাকেট সিকোয়েন্সের সংখ্যা নির্দেশ করে। এখন, সিকোয়েন্সটিকে $k$ এবং ${n - k}$ দৈর্ঘ্যের ২টি অংশে ভাগ করা যায়, যার প্রতিটি একটি সঠিক ব্র্যাকেট সিকোয়েন্স হওয়া উচিত। উদাহরণ:

$( ) ( ( ) )$-কে $( )$ এবং $( ( ) )$-এ ভাগ করা যায়, কিন্তু $( ) ($ এবং $( ) )$-এ ভাগ করা যায় না। আবার সব গ্রহণযোগ্য $k$-এর উপর যোগফল করলে আমরা $C_n$-এর রিকারেন্স সম্পর্ক পাই।

C++ ইমপ্লিমেন্টেশন#

const int MOD = ....
const int MAX = ....
int catalan[MAX];
void init() {
    catalan[0] = catalan[1] = 1;
    for (int i=2; i<=n; i++) {
        catalan[i] = 0;
        for (int j=0; j < i; j++) {
            catalan[i] += (catalan[j] * catalan[i-j-1]) % MOD;
            if (catalan[i] >= MOD) {
                catalan[i] -= MOD;
            }
        }
    }
}

বিশ্লেষণাত্মক সূত্র#

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

(এখানে $\binom{n}{k}$ হলো সাধারণ দ্বিপদী সহগ, অর্থাৎ $n$টি অবজেক্ট থেকে $k$টি অবজেক্ট বাছাই করার উপায়ের সংখ্যা)।

উপরের সূত্রটি বর্গাকার গ্রিডে মনোটনিক পাথের সমস্যা থেকে সহজেই বের করা যায়। $n \times n$ আকারের ল্যাটিসে মনোটনিক পাথের মোট সংখ্যা হলো $\binom{2n}{n}$।

এখন আমরা সেই মনোটনিক পাথের সংখ্যা গুনব যেগুলো মূল কর্ণ অতিক্রম করে। এমন পাথগুলো বিবেচনা করি যেগুলো মূল কর্ণ অতিক্রম করে এবং এর মধ্যে প্রথম এজটি খুঁজে বের করি যেটি কর্ণের উপরে। এই এজের পর থেকে বাকি পাথটি কর্ণের সাপেক্ষে প্রতিফলিত করি। ফলাফল সবসময় $(n - 1) \times (n + 1)$ গ্রিডে একটি মনোটনিক পাথ হয়। অন্যদিকে, $(n - 1) \times (n + 1)$ ল্যাটিসে যেকোনো মনোটনিক পাথ অবশ্যই কর্ণকে ছেদ করবে। অতএব, আমরা $n \times n$ ল্যাটিসে মূল কর্ণ অতিক্রমকারী সব মনোটনিক পাথ গুনে ফেলেছি।

$(n - 1) \times (n + 1)$ ল্যাটিসে মনোটনিক পাথের সংখ্যা হলো $\binom{2n}{n-1}$। আমরা এই পাথগুলোকে “খারাপ” পাথ বলি। ফলে, মূল কর্ণ অতিক্রম করে না এমন মনোটনিক পাথের সংখ্যা পেতে, আমরা উপরের “খারাপ” পাথগুলো বাদ দিই এবং সূত্রটি পাই:

$$C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n + 1} \binom{2n}{n} , {n} \geq 0$$

রেফারেন্স#

অনুশীলন সমস্যা#