Algoritmi → Matematički algoritmi → Kombinatorika: brojanje rasporeda i izbora

Kombinatorika: brojanje rasporeda i izbora

Kombinatorika odgovara na pitanje „na koliko načina…?“ bez ispisivanja svih mogućnosti. Na takmičenjima se rezultat obično traži po modulu 109+7, pa ovde učimo i kako se to računa brzo i bez prekoračenja.

Pre nego što počneš: potrebno predznanje – Matematički algoritmi, Algoritam brzog stepenovanja.
Kako da učiš: svaki primer prekucaj i pokreni, a zadatke na kraju prvo reši sam/a; uputstvo i rešenje otvori tek posle toga. Svi programi su u C++-u.

Pravilo zbira i pravilo proizvoda

  • Pravilo zbira: ako se bira ili jedna od a mogućnosti ili jedna od b (koje se ne preklapaju), ukupno ima a + b mogućnosti.
  • Pravilo proizvoda: ako se bira jedna od a mogućnosti i nezavisno jedna od b, ukupno ima a · b mogućnosti.

Primer: lozinka od 2 slova (26 mogućnosti) iza kojih slede 3 cifre (10 mogućnosti) – ukupno 26 · 26 · 10 · 10 · 10 = 676 000 lozinki.

Osnovne formule

Šta se brojiFormulaPrimer
rasporedi n različitih elemenata (permutacije)n!5 knjiga na polici: 120
uređen izbor k od n (varijacije)n! / (n−k)!prva tri mesta od 10 takmičara: 720
neuređen izbor k od n (kombinacije)C(n, k) = n! / (k!·(n−k)!)tim od 3 od 10 učenika: 120
k puta po jedan od n, sa ponavljanjemnkPIN od 4 cifre: 10 000
putevi u mreži a × b (samo desno i dole)C(a + b, a)mreža 2 × 2: 6

Ako treba ispisati sve te mogućnosti, a ne samo prebrojati ih, vidi Generisanje permutacija i kombinacija.

Paskalov trougao

Za C(n, k) važi C(n, k) = C(n−1, k−1) + C(n−1, k): element n ili jeste u izboru (pa biramo još k−1 od ostalih n−1) ili nije (biramo svih k od n−1). Tako se cela tabela računa samo sabiranjem – bez deljenja, pa radi i po modulu. Ovo je ujedno primer dinamičkog programiranja.

#include <iostream>
using namespace std;

const int MOD = 1000000007;
int C[1001][1001];

int main() {
    for (int n = 0; n <= 1000; n++) {
        C[n][0] = 1;
        for (int k = 1; k <= n; k++)
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % MOD;
    }
    int n, k;
    cin >> n >> k;
    cout << C[n][k] << endl;
    return 0;
}

Tabela 1001 × 1001 se računa za oko pola miliona sabiranja – brzo, ali za n do 106 ne bi stala u memoriju.

Velike vrednosti: faktorijeli po modulu i inverz

Za veliko n unapred se izračunaju faktorijeli f[i] = i! mod p. Deljenje po modulu se zamenjuje množenjem inverzom: kada je p prost broj, inverz broja a je ap−2 mod p (mala Fermaova teorema), a računa se brzim stepenovanjem.

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;          // prost broj
const int MAXN = 1000000;
vector<long long> f(MAXN + 1), invf(MAXN + 1);

long long stepen(long long a, long long b) {
    long long r = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return f[n] * invf[k] % MOD * invf[n - k] % MOD;
}

int main() {
    f[0] = 1;
    for (int i = 1; i <= MAXN; i++) f[i] = f[i - 1] * i % MOD;
    invf[MAXN] = stepen(f[MAXN], MOD - 2);             // inverz najvećeg faktorijela
    for (int i = MAXN; i > 0; i--) invf[i - 1] = invf[i] * i % MOD;

    int q;
    cin >> q;
    while (q--) {
        int n, k;
        cin >> n >> k;
        cout << C(n, k) << "\n";
    }
    return 0;
}

Posle pripreme (oko 2 miliona množenja) svaki upit C(n, k) traje konstantno vreme. Napomena: inverz postoji samo kada p ne deli broj – zato se uzima veliki prost modul.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

ZADATAK 01Težina: Lako

Broj lozinki

Lozinka ima tačno n znakova (n ≤ 1018); svaki znak je malo slovo (26) ili cifra (10). Koliko ima lozinki? Ispiši rezultat po modulu 109+7.

Primer 1

Ulaz

2

Izlaz

1296

Primer 2

Ulaz

1000000000000

Izlaz

231007120
ZADATAK 02Težina: Srednje teško

Putevi kroz grad

Ulice grada čine mrežu sa a blokova udesno i b blokova nadole (a, b ≤ 106). Koliko ima najkraćih puteva od gornjeg levog do donjeg desnog ugla? Rezultat po modulu 109+7.

Primer 1

Ulaz

2 2

Izlaz

6

Primer 2

Ulaz

1000000 1000000

Izlaz

192151600
ZADATAK 03Težina: Lako

Rukovanja i turnir

Na skupu je n ljudi (n ≤ 109) i svako se rukuje sa svakim jednom. Koliko je bilo rukovanja? Ispiši i koliko bi utakmica imao turnir u kome svaka dva tima igraju dva puta (domaćin i gost).

Primer 1

Ulaz

4

Izlaz

6
12

Primer 2

Ulaz

1000000000

Izlaz

499999999500000000
999999999000000000
Česte greške i saveti
  • Pre računanja odluči: da li je redosled bitan (varijacije/permutacije) ili nije (kombinacije)?
  • Po modulu se smeju sabirati, oduzimati i množiti, ali ne i deliti – deljenje se zamenjuje množenjem inverzom.
  • Proizvod dva broja manja od 109+7 staje u long long, ali proizvod tri ne – posle svakog množenja uzmi % MOD.
  • Kod oduzimanja po modulu dodaj MOD: (a - b + MOD) % MOD.

Proveri znanje

Otvori kviz

Mini kviz: kombinatorika

1. Na koliko načina se od 6 učenika bira predsednik i zamenik?




2. Koliko je C(6, 2)?




3. Čime se po prostom modulu p zamenjuje deljenje sa a?