پرش به محتویات

ضرایب دوجمله‌ای

ضرایب دوجمله‌ای $\binom n k$ تعداد راه‌های انتخاب یک مجموعه k عضوی از n عضو متفاوت، بدون در نظر گرفتن ترتیب چیدمان این اعضا است (یعنی، تعداد مجموعه‌های غیرمرتب).

ضرایب دوجمله‌ای همچنین ضرایب بسط عبارت $(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 $$

باور بر این است که این فرمول و همچنین مثلثی که امکان محاسبه سریع ضرایب را فراهم می‌کند، توسط بلز پاسکال در قرن هفدهم کشف شده است. با این وجود، این موارد برای ریاضیدان چینی، یانگ هوی که در قرن سیزدهم زندگی می‌کرد، شناخته شده بود. شاید این فرمول توسط دانشمند ایرانی، عمر خیام کشف شده باشد. علاوه بر این، ریاضیدان هندی، پینگالا، که پیشتر در قرن سوم پیش از میلاد زندگی می‌کرد، به نتایج مشابهی دست یافته بود. شایستگی نیوتن در این است که او این فرمول را برای توان‌هایی که طبیعی نیستند، تعمیم داد.

محاسبه

فرمول تحلیلی برای محاسبه:

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

این فرمول را می‌توان به راحتی از مسئله چیدمان مرتب استنتاج کرد (تعداد راه‌های انتخاب k عضو متفاوت از n عضو متفاوت). ابتدا تعداد انتخاب‌های مرتب k عضو را می‌شماریم. n راه برای انتخاب عضو اول، n-۱ راه برای انتخاب عضو دوم، n-۲ راه برای انتخاب عضو سوم و به همین ترتیب وجود دارد. در نتیجه، به فرمول تعداد چیدمان‌های مرتب می‌رسیم: $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 نیز دچار سرریز (overflow) می‌شود (حتی اگر پاسخ نهایی کاملاً در یک نوع داده جای بگیرد، محاسبه فاکتوریل‌های میانی می‌تواند منجر به سرریز شود). بنابراین، این روش اغلب فقط با استفاده از محاسبات با اعداد بزرگ قابل استفاده است:

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);
}

در اینجا ما با دقت عدد اعشاری را به یک عدد صحیح تبدیل می‌کنیم، با در نظر گرفتن این که به دلیل خطاهای انباشته شده، ممکن است مقدار آن کمی کمتر از مقدار واقعی باشد (برای مثال، ۲.۹۹۹۹۹ به جای ۳).

مثلث پاسکال

با استفاده از رابطه بازگشتی می‌توانیم جدولی از ضرایب دوجمله‌ای (مثلث پاسکال) بسازیم و نتیجه را از آن برداریم. مزیت این روش این است که نتایج میانی هرگز از پاسخ نهایی تجاوز نمی‌کنند و محاسبه هر عنصر جدید جدول تنها به یک عمل جمع نیاز دارد. نقطه ضعف آن، اجرای کند برای 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-۱-ام قبلی) کافی است.

محاسبه در $O(1)$

در نهایت، در برخی شرایط، پیش‌محاسبه تمام فاکتوریل‌ها برای به دست آوردن هر ضریب دوجمله‌ای مورد نیاز تنها با دو تقسیم، سودمند است. این روش هنگام استفاده از محاسبات با اعداد بزرگ می‌تواند مفید باشد، زمانی که حافظه اجازه پیش‌محاسبه کل مثلث پاسکال را نمی‌دهد.

محاسبه ضرایب دوجمله‌ای به پیمانه $m$

اغلب با مسئله محاسبه ضرایب دوجمله‌ای به پیمانه یک عدد $m$ مواجه می‌شوید.

ضریب دوجمله‌ای برای n کوچک

رویکرد مثلث پاسکال که قبلاً مورد بحث قرار گرفت، می‌تواند برای محاسبه تمام مقادیر $\binom{n}{k} \bmod m$ برای nهای منطقاً کوچک استفاده شود، زیرا به پیچیدگی زمانی $\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.$$

ابتدا تمام فاکتوریل‌ها به پیمانه $m$ تا $\text{MAXN}!$ را در زمان $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}$ باشد. می‌توانیم ضریب دوجمله‌ای را به پیمانه $p_i^{e_i}$ برای هر $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$ اول نیست اما خالی از مربع (square-free) است، می‌توان عوامل اول $m$ را به دست آورد و ضریب را به پیمانه هر عامل اول با استفاده از یکی از روش‌های بالا محاسبه کرد و پاسخ کلی را با قضیه باقیمانده چینی به دست آورد.

وقتی $m$ خالی از مربع نیست، می‌توان به جای قضیه لوکاس از تعمیم قضیه لوکاس برای توان‌های اول استفاده کرد.

مسائل تمرینی

منابع