Binomial koeffitsiyentlar
Binomial koeffitsiyentlar — bu ta turli elementdan ta elementdan iborat to‘plamni tanlash usullari soni tartibni hisobga olmasdan (ya’ni tartiblanmagan to‘plamlar soni).
Binomial koeffitsiyentlar yoyilmasidagi koeffitsiyentlar hamdir (binomial teorema):
Analitik formula:
Rekurrent formula (Paskal uchburchagi bilan bog‘liq):
E’tibor bering, bo‘lsa, qiymati nolga teng deb hisoblanadi.
Binomial koeffitsiyentlar ko‘plab foydali xossalarga ega. Asosiylarini keltiramiz.
Kodda:
vector<vector<int>> C(N, vector<int> (N, 0));
for (int i = 0; i < N; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
void init_combinatorics() {
fac[0] = 1;
for (int i = 1; i < N; i++) {
fac[i] = 1ll * i * fac[i - 1] % mod;
}
inv[N - 1] = pw(fac[N - 1], mod - 2);
for (int i = N - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * 1ll * (i + 1) % mod;
}
}
int C(int n, int k) {
return 1ll * fac[n] * inv[k] % mod * inv[n - k] % mod;
}