Combinări

O combinare de n luate câte k e o alegere neordonată a k elemente dintr-o mulțime de n elemente.

Ordinea NU contează și elementele nu se repetă.

Formula

C(n, k) = n! / (k! * (n-k)!)

Se citește “n combinat k” sau “coeficient binomial”. Notații alternative: C(n,k), ₙCₖ, (n k) (în formă de matrice coloană), binomial(n, k).

De unde vine?

Aranjamente ordonate: A(n, k) = n!/(n-k)!.

Pentru fiecare grup de k elemente, există k! moduri de a le ordona. Împărțim ca să numărăm fiecare grup o singură dată:

C(n, k) = A(n, k) / k! = n! / (k! * (n-k)!)

Valori mici

(Triunghiul lui Pascal - vezi lecția următoare.)

Exemple

Exemplul 1: echipă

Din 10 elevi, câte echipe de 3 se pot forma?

→ C(10, 3) = 10!/(3! * 7!) = 120.

Exemplul 2: loto

La 6/49, câte variante diferite sunt?

→ C(49, 6) = 13.983.816.

Exemplul 3: mâini de cărți

Câte mâini de 5 cărți se pot împărți dintr-un pachet de 52?

→ C(52, 5) = 2.598.960.

Proprietăți importante

1. Simetria

C(n, k) = C(n, n-k)

Alegerea a k elemente e echivalentă cu “neselecția” a n-k. Același număr.

Exemplu: C(10, 3) = C(10, 7) = 120.

2. Regula lui Pascal

C(n, k) = C(n-1, k-1) + C(n-1, k)

Fie un element fix (de ex. primul). Combinările de k:

• Conțin primul element: alegem celelalte k-1 din restul n-1 → C(n-1, k-1)
• Nu conțin primul element: alegem k din restul n-1 → C(n-1, k)

Total: sumă.

3. Sumă pe linie

C(n, 0) + C(n, 1) + … + C(n, n) = 2^n

Suma tuturor submulțimilor unei mulțimi de n elemente = 2^n (fiecare element ales sau nu).

4. Cazuri speciale

C(n, 0) = 1       (o singură mulțime vidă)
C(n, n) = 1       (o singură mulțime completă)
C(n, 1) = n       (n submulțimi cu 1 element)
C(n, k) = 0 dacă k > n sau k < 0

Calcularea eficientă

1. Cu factoriale

long long factorial(int n) {
    long long rez = 1;
    for (int i = 2; i <= n; i++) rez *= i;
    return rez;
}

long long combinari(int n, int k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

Problemă: factorialele devin rapid overflow. 20! = 2.4 * 10^18 încape în long long, dar 21! nu.

2. Produs direct (mai stabil)

long long combinari(int n, int k) {
    if (k > n - k) k = n - k; // simetrie - minim = mai rapid
    long long rez = 1;
    for (int i = 0; i < k; i++) {
        rez *= (n - i);
        rez /= (i + 1);
    }
    return rez;
}

Pentru C(10, 3):

i=0: rez = 1 * 10 / 1 = 10
i=1: rez = 10 * 9 / 2 = 45
i=2: rez = 45 * 8 / 3 = 120

De ce funcționează împărțirea exactă? La fiecare pas, rez * (n-i) e divizibil cu (i+1) (proprietatea coeficienților binomiali).

3. Cu Pascal (iterativ)

Precalculăm C(i, j) pentru toate i, j ≤ n:

long long C[1001][1001];

void precalculare(int n) {
    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-1] + C[i-1][j];
    }
}

O(n²) timp, O(n²) memorie. Util dacă avem multe interogări.

4. Cu factoriale mod prim

Pentru rezultat mod p (prim), folosim invers modular:

long long fact[MAXN], invFact[MAXN];
const long long MOD = 1000000007;

long long putere(long long a, long long e, long long m) {
    long long r = 1;
    a %= m;
    while (e > 0) {
        if (e & 1) r = r * a % m;
        a = a * a % m;
        e >>= 1;
    }
    return r;
}

void precalculare(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    invFact[n] = putere(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--)
        invFact[i] = invFact[i+1] * (i+1) % MOD;
}

long long combinari(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
}

O(n) precalcul + O(1) per interogare.

Cod complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

long long combinari(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    long long rez = 1;
    for (int i = 0; i < k; i++) {
        rez *= (n - i);
        rez /= (i + 1);
    }
    return rez;
}

int main() {
    int n, k;
    fin >> n >> k;
    fout << "C(" << n << ", " << k << ") = " << combinari(n, k);
    return 0;
}

date.in:

10 3

date.out:

C(10, 3) = 120

Probleme clasice

1. Submulțimi

Câte submulțimi de k elemente are o mulțime cu n elemente?

→ C(n, k).

2. Drumuri pe grilă

De la (0,0) la (m,n), mergând doar dreapta sau sus, câte drumuri sunt?

Facem m+n pași: m la dreapta, n în sus. Alegem care m din m+n pași sunt la dreapta.

→ C(m+n, m).

3. Strângere de mâini

Câte strângeri de mâini au loc într-un grup de n oameni dacă fiecare dă mâna cu fiecare?

→ C(n, 2) = n(n-1)/2.

4. Diagonale într-un poligon

Câte diagonale are un poligon cu n laturi?

→ C(n, 2) - n (perechi de vârfuri, minus laturile).

Greșeli frecvente

1. Overflow la factorial

21! nu mai încape în long long. Folosește produsul direct sau aritmetică modulară.

2. Împărțire imprecisă (float)

double rez = factorial(n) / (factorial(k) * factorial(n-k)); // RISC

Folosește întregi cu împărțire exactă (produsul direct sau Pascal).

3. k > n sau k < 0

C(5, 7) = 0 prin convenție. Verifică întotdeauna limitele.

4. Confuzia aranjament/combinare

“Câte echipe?” → combinări. “Câte așezări pe podium?” → aranjamente.

Ordinea contează?

Ce să reții

• Combinare = alegere neordonată de k din n.
• C(n, k) = n! / (k! * (n-k)!).
• Proprietăți: C(n,k) = C(n,n-k), C(n,k) = C(n-1,k-1) + C(n-1,k), ΣC(n,k) = 2^n.
• Calcul eficient: produs direct (fără factoriale) sau precalcul Pascal.
• Pentru mod prim: folosește invers modular cu Fermat.
• Cazuri speciale: C(n,0) = C(n,n) = 1, C(n,k) = 0 dacă k > n.