Агуулгыг алгасах

Биномын коэффициент

Биномын коэффициент $\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 $$

Энэ томьёо болон коэффициентүүдийг үр ашигтай тооцоолох боломж олгодог гурвалжныг 17-р зуунд Блез Паскаль нээсэн гэж үздэг. Гэсэн хэдий ч үүнийг 13-р зуунд амьдарч байсан Хятадын математикч Ян Хуй мэддэг байсан. Магадгүй үүнийг Персийн эрдэмтэн Омар Хайям нээсэн байж болох. Түүнчлэн МЭӨ 3-р зуунд амьдарч байсан Энэтхэгийн математикч Пингала ижил төстэй үр дүнд хүрсэн. Ньютоны гавьяа нь энэ томьёог натурал биш зэрэг илтгэгчийн хувьд ерөнхийлсөнд оршино.

Тооцоолол

Тооцоолох аналитик томьёо:

$$ \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$), тус бүр нь 1-ээс их буюу тэнцүү болохыг анхаарна уу. Тиймээс бид бутархайгаа тус бүр нь бодит утгатай $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)$ хүртэлх хүснэгт байгуулах шаардлагатай). Time complexity-г $\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)$ time complexity шаарддаг. Зөвхөн нэмэх үйлдэл ашигладаг тул энэ арга дурын модулийг зохицуулж чадна.

Том анхны тооны модулиар биномын коэффициент

Биномын коэффициентийн томьёо нь

$$\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(\text{MAXN} \log m)$-д, эсвэл бүр $(x!)^{-1} \equiv ((x-1)!)^{-1} \cdot x^{-1}$ congruence ба $O(n)$-д бүх урвуутайг тооцоолох аргыг ашиглан $O(\text{MAXN})$ хугацаанд урьдчилан тооцоолбол биномын коэффициентийг бүр $O(1)$ хугацаанд ч тооцоолж болно.

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

Анхны тооны зэргийн модулиар биномын коэффициент

Энд бид биномын коэффициентийг ямар нэг анхны тооны зэргийн модулиар буюу ямар нэг анхны $p$-ийн хувьд $m = p^b$ модулиар тооцоолохыг хүсэж байна. Хэрэв $p > \max(k, n-k)$ бол бид өмнөх хэсэгт тайлбарласан ижил аргыг ашиглаж болно. Гэвч хэрэв $p \le \max(k, n-k)$ бол $k!$ ба $(n-k)!$-ийн дор хаяж нэг нь $m$-тэй харилцан анхны биш тул бид урвуутайг тооцоолж чадахгүй — тэдгээр нь оршихгүй. Гэсэн хэдий ч бид биномын коэффициентийг тооцоолж болно.

Санаа нь дараах: Бид $x!$ бүрийн хувьд $p^c$ нь $x!$-г хуваах хамгийн их илтгэгч $c$-г буюу $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)$-ийн модулийн урвуутайг тооцоолж болно.

Динамик программчлал ашиглан $\mathcal{O}(n)$-д үр ашигтайгаар хийж болох $g$ ба $c$-ийн бүх утгыг урьдчилан тооцоолсны дараа бид биномын коэффициентийг $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$ ялгаатай congruence өгнө. Бүх $p_i^{e_i}$ модулиуд харилцан анхны тул бид Хятадын үлдэгдлийн теорем-ыг хэрэглэн модулиудын үржвэрийн модулиар биномын коэффициентийг тооцоолж болох ба энэ нь $m$ модулиар хайж буй биномын коэффициент юм.

Том $n$ ба бага модулийн хувьд биномын коэффициент

$n$ хэт том үед дээр авч үзсэн $\mathcal{O}(n)$ алгоритмууд практик бус болно. Гэвч хэрэв $m$ модуль бага бол $\binom{n}{k} \bmod m$-г тооцоолох аргууд байсаар байна.

$m$ модуль анхны үед 2 сонголт бий:

  • Лукасын теорем-ыг хэрэглэж болох ба энэ нь $\binom{n}{k} \bmod m$-г тооцоолох бодлогыг $x_i, y_i < m$ байх $\binom{x_i}{y_i} \bmod m$ хэлбэрийн $\log_m n$ бодлого болгон хуваадаг. Хэрэв хураагдсан коэффициент бүрийг урьдчилан тооцоолсон факториал ба урвуу факториал ашиглан тооцоолбол complexity нь $\mathcal{O}(m + \log_m n)$ болно.
  • P модулиар факториал тооцоолох аргыг ашиглан шаардлагатай $g$ ба $c$ утгуудыг олж, анхны тооны зэргийн модулиар хэсэгт тайлбарласнаар ашиглаж болно. Энэ нь $\mathcal{O}(m \log_m n)$ авна.

$m$ анхны биш боловч квадратгүй үед $m$-ийн анхны үржигдэхүүнүүдийг олж, анхны үржигдэхүүн бүрийн модулиар коэффициентийг дээрх аргуудын аль нэгээр тооцоолж, ерөнхий хариуг Хятадын үлдэгдлийн теоремоор олж болно.

$m$ квадратгүй биш үед Лукасын теоремын оронд анхны тооны зэргийн хувьд Лукасын теоремын ерөнхийлөл-ийг хэрэглэж болно.

Дасгал бодлогууд

Ашигласан материал