Numărarea combinărilor — alegi fără ordine

De ce contează?

Ai 4 colegi și vrei să formezi o echipă de 2 pentru un proiect. Câte echipe diferite poți face? Observă: echipa „Ana și Bogdan" este aceeași cu „Bogdan și Ana" — nu contează cine a fost ales primul. Atunci când ordinea nu contează, nu mai numeri aranjamente, ci combinări.

De ce C(n,k) = n! / (k!·(n-k)!)

O combinare C(n,k) numără în câte moduri poți alege k elemente din n, fără să conteze ordinea alegerii.

Pornește de la aranjamente. Numărul de aranjamente A(n,k) = n! / (n-k)! numără alegerile ordonate de k elemente. Dar la combinări, fiecare grup de k elemente a fost numărat de mai multe ori — exact de câte ori poți rearanja acele k elemente între ele, adică k! ori (permutările lor interne).

Ca să eliminăm dublurile, împărțim la k!:

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

De aici iese imediat și simetria: a alege k elemente pe care le iei este totuna cu a alege cele n-k pe care le lași afară. Deci:

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

Exemplu pas cu pas: C(4,2) = 6

Hai să numărăm direct toate echipele de 2 din {A, B, C, D}:

{A,B}, {A,C}, {A,D}
{B,C}, {B,D}
{C,D}

Sunt 6 echipe. Verifică cu formula:

C(4,2) = 4! / (2!·2!) = 24 / (2·2) = 24 / 4 = 6

Dacă ai fi numărat aranjamente, ai fi avut A(4,2) = 12 (de exemplu AB și BA separat). Împărțind la 2! = 2, obții tot 6.

Folosind simetria: C(4,2) = C(4, 4-2) = C(4,2) — aici k = n-k, caz special. Dar C(4,1) = C(4,3) = 4, iar C(4,0) = C(4,4) = 1 (un singur mod de a nu alege nimic, respectiv de a alege tot).

Implementare C++ (triunghiul lui Pascal)

În loc să calculezi factoriale uriașe și să împarți, construiește direct triunghiul cu relația C(n,k) = C(n-1,k-1) + C(n-1,k). Folosești doar adunări, deci eviți și overflow-ul, și împărțirea.

#include <iostream>
using namespace std;

const int MOD = 1000000007;
const int N = 1000;

long long C[N + 1][N + 1];

void construiestePascal() {
    for (int n = 0; n <= N; n++) {
        C[n][0] = 1;            // un singur mod de a alege 0 elemente
        for (int k = 1; k <= n; k++) {
            // suma celor doi termeni de deasupra; modulo pentru numere mari
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % MOD;
        }
    }
}

int main() {
    construiestePascal();

    cout << C[4][2] << "\n";    // 6
    cout << C[5][2] << "\n";    // 10
    cout << C[4][0] << "\n";    // 1
    cout << C[4][4] << "\n";    // 1
    return 0;
}

Dacă valorile sunt mici și nu ai nevoie de modulo, scoți % MOD și long long ține rezultatul exact până pe la n = 60 aproximativ. Pentru n mare folosește mereu long long + MOD.

Complexitate

Operație	Timp	Spațiu
Construire tabel Pascal	O(n·k)	O(n·k)
Citire `C[n][k]` după construire	O(1)	—
Formula directă cu factoriale	O(n)	O(1)

Tabelul Pascal îl construiești o singură dată, apoi răspunzi la orice întrebare C[n][k] instant. E ideal când ai multe interogări cu n mic sau mediu.

Observația-cheie

Triunghiul lui Pascal calculează combinări fără nicio împărțire — doar adunări de numere mici. Asta îl face perfect pentru lucrul modulo un prim: adunarea se comportă cuminte la % MOD, pe când împărțirea cere invers modular.

Greșeli frecvente

Calcul direct cu factoriale → overflow: n! crește exploziv. Deja 21! depășește un long long. Nu calcula n! separat decât pentru n foarte mic; preferă Pascal.
Uiți C(n,0) = 1: linia C[n][0] = 1 e baza recurenței. Fără ea, tot triunghiul iese zero.
Confuzi combinări cu aranjamente: la aranjamente ordinea contează (AB ≠ BA). Dacă numeri echipe, mâini de cărți sau submulțimi, sunt combinări.
Împărțire modulo fără invers: (a / b) % MOD NU este (a % MOD) / (b % MOD). Pentru a împărți modulo un prim ai nevoie de invers modular — vezi lecția „invers-modular". Pascal evită complet problema.

Un rând complet din triunghi, pentru n = 4, conține exact coeficienții C(4,0) … C(4,4):

C(4,k)	1	4	6	4	1
	0	1	2	3	4

Rândul n = 4 din triunghiul lui Pascal. Celula evidențiată este C(4,2) = 6; observă simetria 1 4 6 4 1.

Vizualizare

Indiciu

Observă cum fiecare număr e suma celor doi de deasupra; folosește ← / → pentru a avansa pas cu pas.

Recapitulare

C(n,k) = n! / (k!·(n-k)!) numără alegerile de k din n când ordinea nu contează; vine din aranjamente împărțite la k!.
Simetria C(n,k) = C(n, n-k) și bazele C(n,0) = C(n,n) = 1 te ajută la verificări.
Triunghiul lui Pascal C(n,k) = C(n-1,k-1) + C(n-1,k) calculează cu adunări, evitând overflow-ul și împărțirea — metoda preferată, mai ales modulo un prim.