বাইনোমিয়াল কোএফিশিয়েন্ট (Binomial Coefficient)#

বাইনোমিয়াল কোএফিশিয়েন্ট $\binom n k$ হলো $n$ টি ভিন্ন উপাদান থেকে $k$ টি উপাদানের একটি সেট নির্বাচন করার উপায়ের সংখ্যা, যেখানে এই উপাদানগুলোর সাজানোর ক্রম কনসিডার করা হয় না (অর্থাৎ অক্রমিক সেটের সংখ্যা)।

বাইনোমিয়াল কোএফিশিয়েন্ট $(a + b) ^ n$ এর সম্প্রসারণেও সহগ হিসেবে পাওয়া যায় (তথাকথিত বাইনোমিয়াল থিওরেম):

$$ (a+b)^n = \binom n 0 a^n + \binom n 1 a^{n-1} b + \binom n 2 a^{n-2} b^2 + \cdots + \binom n k a^{n-k} b^k + \cdots + \binom n n b^n $$

এই সূত্রটি, সেইসাথে যে ত্রিভুজ সহগগুলোর দক্ষ হিসাবের সুবিধা দেয়, সেটা১৭শ শতকে Blaise Pascal আবিষ্কার করেছিলেন বলে মনে করা হয়। তবুও, এটা১৩শ শতকে বাসকারী চীনা গণিতবিদ Yang Hui এর কাছে পরিচিত ছিল। সম্ভবত এটাপারস্যের পণ্ডিত ওমর খৈয়ামও আবিষ্কার করেছিলেন। তাছাড়া, খ্রিস্টপূর্ব ৩য় শতকে বাসকারী ভারতীয় গণিতবিদ পিঙ্গল একই রকম ফলাফল পেয়েছিলেন। নিউটনের কৃতিত্ব হলো তিনি এই সূত্রটি এমন ঘাতের জন্য সাধারণীকরণ করেছেন যা স্বাভাবিক সংখ্যা নয়।

হিসাব#

হিসাবের জন্য বিশ্লেষণাত্মক সূত্র:

$$ \binom n k = \frac {n!} {k!(n-k)!} $$

এই সূত্রটি ক্রমিক সাজানোর সমস্যা থেকে সহজেই বের করা যায় ($n$ টি ভিন্ন উপাদান থেকে $k$ টি ভিন্ন উপাদান নির্বাচনের উপায়ের সংখ্যা)। প্রথমে, $k$ টি উপাদানের ক্রমিক নির্বাচনের সংখ্যা গণনা করি। প্রথম উপাদান নির্বাচনের $n$ টি উপায়, দ্বিতীয় উপাদান নির্বাচনের $n-1$ টি উপায়, তৃতীয় উপাদান নির্বাচনের $n-2$ টি উপায়, ইত্যাদি। ফলে আমরা ক্রমিক সাজানোর সংখ্যার সূত্র পাই: $n (n-1) (n-2) \cdots (n - k + 1) = \frac {n!} {(n-k)!}$। প্রতিটি অক্রমিক সাজানো ঠিক $k!$ টি ক্রমিক সাজানোর সাথে সম্পর্কিত ($k!$ হলো $k$ টি উপাদানের সম্ভাব্য পারমুটেশনের সংখ্যা) - এটালক্ষ করলে আমরা সহজেই অক্রমিক সাজানোতে যেতে পারি। $\frac {n!} {(n-k)!}$ কে $k!$ দিয়ে ভাগ করে আমরা চূড়ান্ত সূত্র পাই।

পুনরাবৃত্তি সূত্র (যা বিখ্যাত “প্যাসকেলের ত্রিভুজ” এর সাথে সম্পর্কিত):

$$ \binom n k = \binom {n-1} {k-1} + \binom {n-1} k $$

বিশ্লেষণাত্মক সূত্র ব্যবহার করে এটাসহজেই বের করা যায়।

লক্ষ্য করো $n \lt k$ হলে $\binom n k$ এর মান শূন্য ধরা হয়।

বৈশিষ্ট্য#

বাইনোমিয়াল কোএফিশিয়েন্টের অনেক বিভিন্ন বৈশিষ্ট্য আছে। এখানে সবচেয়ে সরলগুলো দেওয়া হলো:

  • প্রতিসাম্য নিয়ম:

    \[ \binom n k = \binom n {n-k} \]

  • ফ্যাক্টরাইজেশন:

    \[ \binom n k = \frac n k \binom {n-1} {k-1} \]

  • $k$ এর উপর যোগফল:

    \[ \sum_{k = 0}^n \binom n k = 2 ^ n \]

  • $n$ এর উপর যোগফল:

    \[ \sum_{m = 0}^n \binom m k = \binom {n + 1} {k + 1} \]

  • $n$ এবং $k$ এর উপর যোগফল:

    \[ \sum_{k = 0}^m \binom {n + k} k = \binom {n + m + 1} m \]

  • বর্গের যোগফল:

    \[ {\binom n 0}^2 + {\binom n 1}^2 + \cdots + {\binom n n}^2 = \binom {2n} n \]

  • ভারযুক্ত যোগফল:

    \[ 1 \binom n 1 + 2 \binom n 2 + \cdots + n \binom n n = n 2^{n-1} \]

  • ফিবোনাচ্চি সংখ্যার সাথে সম্পর্ক:

    \[ \binom n 0 + \binom {n-1} 1 + \cdots + \binom {n-k} k + \cdots + \binom 0 n = F_{n+1} \]

হিসাব#

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

প্রথম, সরাসরি সূত্রটি কোড করা খুব সহজ, কিন্তু এই পদ্ধতি $n$ এবং $k$ এর তুলনামূলকভাবে ছোট মানের জন্যও ওভারফ্লো হতে পারে (এমনকি উত্তর কোনো ডেটাটাইপে সম্পূর্ণ ফিট করলেও, মধ্যবর্তী ফ্যাক্টোরিয়ালের হিসাব ওভারফ্লো ঘটাতে পারে)। তাই এই পদ্ধতি প্রায়ই শুধুমাত্র বড় সংখ্যার গাণিতিক দিয়ে ব্যবহার করা যায়:

int C(int n, int k) {
    int res = 1;
    for (int i = n - k + 1; i <= n; ++i)
        res *= i;
    for (int i = 2; i <= k; ++i)
        res /= i;
    return res;
}

উন্নত ইমপ্লিমেন্টেশন#

লক্ষ্য করো উপরের ইমপ্লিমেন্টেশনে লব ও হরে সমান সংখ্যক ($k$ টি) ফ্যাক্টর আছে, যার প্রতিটি ১ বা তার বেশি। তাই আমরা আমাদের ফ্র্যাকশনকে $k$ টি ফ্র্যাকশনের গুণফল দিয়ে প্রতিস্থাপন করতে পারি, যার প্রতিটি বাস্তব মানযুক্ত। তবে, প্রতিটি ধাপে বর্তমান উত্তরকে পরবর্তী ফ্র্যাকশন দিয়ে গুণ করার পর উত্তর এখনো পূর্ণ সংখ্যা থাকবে (এটাফ্যাক্টরাইজেশন বৈশিষ্ট্য থেকে অনুসরণ করে)।

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

int C(int n, int k) {
    double res = 1;
    for (int i = 1; i <= k; ++i)
        res = res * (n - k + i) / i;
    return (int)(res + 0.01);
}

এখানে আমরা সাবধানে ফ্লোটিং পয়েন্ট সংখ্যাকে পূর্ণ সংখ্যায় রূপান্তর করি, কনসিডার করে যে জমা হওয়া ত্রুটির কারণে এটাপ্রকৃত মানের চেয়ে সামান্য কম হতে পারে (যেমন, $3$ এর পরিবর্তে $2.99999$)।

প্যাসকেলের ত্রিভুজ#

পুনরাবৃত্তি সম্পর্ক ব্যবহার করে আমরা বাইনোমিয়াল কোএফিশিয়েন্টের একটি সারণী (প্যাসকেলের ত্রিভুজ) তৈরি করতে পারি এবং সেখান থেকে ফলাফল নিতে পারি। এই পদ্ধতির সুবিধা হলো মধ্যবর্তী ফলাফল কখনো উত্তরকে অতিক্রম করে না এবং প্রতিটি নতুন সারণী উপাদান হিসাবে শুধুমাত্র একটি যোগ প্রয়োজন। ত্রুটি হলো বড় $n$ এবং $k$ এর জন্য ধীর কার্যকারিতা যদি তোমার শুধু একটি মান দরকার হয় পুরো সারণী নয় (কারণ $\binom n k$ হিসাব করতে সব $\binom i j, 1 \le i \le n, 1 \le j \le n$ বা অন্তত $1 \le j \le \min (i, 2k)$ পর্যন্ত সারণী তৈরি করতে হবে)। টাইম কমপ্লেক্সিটি $\mathcal{O}(n^2)$ ধরা যায়।

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

const int maxn = ...;
int C[maxn + 1][maxn + 1];
C[0][0] = 1;
for (int n = 1; n <= maxn; ++n) {
    C[n][0] = C[n][n] = 1;
    for (int k = 1; k < n; ++k)
        C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
}

যদি সম্পূর্ণ মান সারণী প্রয়োজন না হয়, তাহলে শুধু শেষ দুটি সারি (বর্তমান $n$-তম সারি এবং আগের $n-1$-তম) সংরক্ষণ করাই যথেষ্ট।

$O(1)$ এ হিসাব#

শেষত, কিছু পরিস্থিতিতে সব ফ্যাক্টোরিয়াল আগে থেকে হিসাব করে রাখা লাভজনক, যাতে পরে শুধুমাত্র দুটি ভাগ দিয়ে যেকোনো প্রয়োজনীয় বাইনোমিয়াল কোএফিশিয়েন্ট বের করা যায়। বড় সংখ্যার গাণিতিক ব্যবহার করার সময় এটাসুবিধাজনক হতে পারে, যখন মেমরি পুরো প্যাসকেলের ত্রিভুজ আগে থেকে হিসাব করার সুযোগ দেয় না।

$m$ মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাব#

প্রায়ই কোনো $m$ মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাবের সমস্যা সামনে আসে।

ছোট $n$ এর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট#

পূর্বে আলোচিত প্যাসকেলের ত্রিভুজ পদ্ধতি যুক্তিসঙ্গতভাবে ছোট $n$ এর জন্য $\binom{n}{k} \bmod m$ এর সব মান হিসাব করতে ব্যবহার করা যায়, কারণ এর টাইম কমপ্লেক্সিটি $\mathcal{O}(n^2)$। এই পদ্ধতি যেকোনো মডুলো সামলাতে পারে, কারণ শুধুমাত্র যোগ অপারেশন ব্যবহৃত হয়।

বড় মৌলিক মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট#

বাইনোমিয়াল কোএফিশিয়েন্টের সূত্র হলো

$$\binom n k = \frac {n!} {k!(n-k)!},$$

তাই যদি আমরা কোনো মৌলিক $m > n$ মডুলোতে এটাহিসাব করতে চাই তাহলে পাই

$$\binom n k \equiv n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \mod m.$$

প্রথমে আমরা $\text{MAXN}!$ পর্যন্ত সব ফ্যাক্টোরিয়াল $m$ মডুলোতে $O(\text{MAXN})$ সময়ে আগে থেকে হিসাব করি।

factorial[0] = 1;
for (int i = 1; i <= MAXN; i++) {
    factorial[i] = factorial[i - 1] * i % m;
}

এবং তারপর আমরা $O(\log m)$ সময়ে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাব করতে পারি।

long long binomial_coefficient(int n, int k) {
    return factorial[n] * inverse(factorial[k] * factorial[n - k] % m) % m;
}

আমরা $O(1)$ সময়ে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাবও করতে পারি যদি আমরা সব ফ্যাক্টোরিয়ালের ইনভার্স $O(\text{MAXN} \log m)$ সময়ে ইনভার্স হিসাবের সাধারণ পদ্ধতি ব্যবহার করে, অথবা এমনকি $O(\text{MAXN})$ সময়ে $(x!)^{-1} \equiv ((x-1)!)^{-1} \cdot x^{-1}$ সর্বসমতা এবং $O(n)$ এ সব ইনভার্স হিসাবের পদ্ধতি ব্যবহার করে আগে থেকে হিসাব করি।

long long binomial_coefficient(int n, int k) {
    return factorial[n] * inverse_factorial[k] % m * inverse_factorial[n - k] % m;
}

মৌলিক সংখ্যার ঘাত মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট#

এখানে আমরা কোনো মৌলিক সংখ্যার ঘাত মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাব করতে চাই, অর্থাৎ $m = p^b$ কোনো মৌলিক $p$ এর জন্য। যদি $p > \max(k, n-k)$ হয়, তাহলে আমরা আগের সেকশনে দেখানো একই পদ্ধতি ব্যবহার করতে পারি। কিন্তু যদি $p \le \max(k, n-k)$ হয়, তাহলে $k!$ এবং $(n-k)!$ এর অন্তত একটি $m$ এর সাথে সহমৌলিক নয়, এবং তাই আমরা ইনভার্স হিসাব করতে পারি না - সেগুলোর অস্তিত্ব নেই। তবুও আমরা বাইনোমিয়াল কোএফিশিয়েন্ট হিসাব করতে পারি।

ধারণাটা এরকম: আমরা প্রতিটি $x!$ এর জন্য সবচেয়ে বড় ঘাত $c$ হিসাব করি যেন $p^c$ দিয়ে $x!$ কে ভাগ করা যায়, অর্থাৎ $p^c ~|~ x!$। ধরি $c(x)$ হলো সেই সংখ্যা। এবং ধরি $g(x) := \frac{x!}{p^{c(x)}}$। তাহলে আমরা বাইনোমিয়াল কোএফিশিয়েন্ট লিখতে পারি:

$$\binom n k = \frac {g(n) p^{c(n)}} {g(k) p^{c(k)} g(n-k) p^{c(n-k)}} = \frac {g(n)} {g(k) g(n-k)}p^{c(n) - c(k) - c(n-k)}$$

আকর্ষণীয় বিষয় হলো, $g(x)$ এখন মৌলিক ডিভাইজর $p$ থেকে মুক্ত। তাই $g(x)$ হলো $m$ এর সাথে সহমৌলিক, এবং আমরা $g(k)$ ও $g(n-k)$ এর মডুলার ইনভার্স হিসাব করতে পারি।

$g$ এবং $c$ এর সব মান আগে থেকে হিসাব করার পর, যা $\mathcal{O}(n)$ সময়ে ডায়নামিক প্রোগ্রামিং ব্যবহার করে দক্ষতার সাথে করা যায়, আমরা $O(\log m)$ সময়ে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাব করতে পারি। অথবা সব ইনভার্স এবং $p$ এর সব ঘাত আগে থেকে হিসাব করে, $O(1)$ সময়ে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাব করা যায়।

লক্ষ্য করো, যদি $c(n) - c(k) - c(n-k) \ge b$ হয়, তাহলে $p^b ~|~ p^{c(n) - c(k) - c(n-k)}$, এবং বাইনোমিয়াল কোএফিশিয়েন্ট হলো $0$।

যেকোনো সংখ্যা মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট#

এখন আমরা কোনো যেচ্ছা মডুলাস $m$ মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাব করি।

ধরি $m$ এর মৌলিক উৎপাদক বিভাজন হলো $m = p_1^{e_1} p_2^{e_2} \cdots p_h^{e_h}$। আমরা প্রতিটি $i$ এর জন্য $p_i^{e_i}$ মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাব করতে পারি। এটাআমাদের $h$ টি ভিন্ন সর্বসমতা দেয়। যেহেতু সব মডুলাই $p_i^{e_i}$ পরস্পর সহমৌলিক, আমরা চীনা ভাগশেষ থিওরেম প্রয়োগ করে মডুলাইগুলোর গুণফল মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট হিসাব করতে পারি, যা হলো কাঙ্ক্ষিত $m$ মডুলোতে বাইনোমিয়াল কোএফিশিয়েন্ট।

বড় $n$ এবং ছোট মডুলোর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট#

যখন $n$ অনেক বড়, উপরে আলোচিত $\mathcal{O}(n)$ অ্যালগরিদমগুলো অব্যবহারযোগ্য হয়ে যায়। তবে, মডুলো $m$ ছোট হলে $\binom{n}{k} \bmod m$ হিসাবের উপায় এখনো আছে।

মডুলো $m$ মৌলিক হলে, ২টি বিকল্প আছে:

  • লুকাসের থিওরেম প্রয়োগ করা যায় যা $\binom{n}{k} \bmod m$ হিসাবের সমস্যাকে $\log_m n$ টি $\binom{x_i}{y_i} \bmod m$ আকারের সমস্যায় ভেঙে দেয় যেখানে $x_i, y_i < m$। যদি প্রতিটি হ্রাসকৃত সহগ আগে থেকে হিসাবকৃত ফ্যাক্টোরিয়াল ও ইনভার্স ফ্যাক্টোরিয়াল ব্যবহার করে হিসাব করা হয়, কমপ্লেক্সিটি হলো $\mathcal{O}(m + \log_m n)$।
  • P মডুলোতে ফ্যাক্টোরিয়াল হিসাবের পদ্ধতি ব্যবহার করে প্রয়োজনীয় $g$ এবং $c$ মান পেয়ে মৌলিক সংখ্যার ঘাত মডুলো বিভাগে বর্ণিত মতো ব্যবহার করা যায়। এটা$\mathcal{O}(m \log_m n)$ সময় নেয়।

যখন $m$ মৌলিক নয় কিন্তু বর্গমুক্ত, $m$ এর মৌলিক ফ্যাক্টর পাওয়া যায় এবং উপরের যেকোনো পদ্ধতি ব্যবহার করে প্রতিটি মৌলিক ফ্যাক্টর মডুলোতে সহগ হিসাব করা যায়, এবং চীনা ভাগশেষ থিওরেম দিয়ে সামগ্রিক উত্তর পাওয়া যায়।

যখন $m$ বর্গমুক্ত নয়, লুকাসের থিওরেমের পরিবর্তে মৌলিক সংখ্যার ঘাতের জন্য লুকাসের থিওরেমের সাধারণীকরণ প্রয়োগ করা যায়।

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

রেফারেন্স#