দ্বিপদী সহগ#

দ্বিপদী সহগ $\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$ বর্গমুক্ত নয়, লুকাসের উপপাদ্যের পরিবর্তে মৌলিক সংখ্যার ঘাতের জন্য লুকাসের উপপাদ্যের সাধারণীকরণ প্রয়োগ করা যায়।

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

রেফারেন্স#