Коэффисиентҳои биномиалӣ
Коэффисиентҳои биномиалӣ шумораи роҳҳои интихоб кардани маҷмӯи унсур аз унсури фарқкунанда бе назардошти тартиб мебошанд (яъне, шумораи маҷмӯаҳои бетартиб).
Коэффисиентҳои биномиалӣ инчунин коэффисиентҳо дар густариши мебошанд (теоремаи биномиалӣ):
Формулаи аналитикӣ:
Формулаи рекурсивӣ (марбут ба секунҷаи Паскал):
Қайд кунед, ки барои , қимати сифр ҳисобида мешавад.
Коэффисиентҳои биномиалӣ хосиятҳои зиёди муфид доранд. Инҳо асоситаринашон мебошанд.
Дар код:
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;
}