De ce contează?
Ai un grup de 4 prieteni și vrei să iei 2 dintre ei la film. „Ana și Bogdan” e exact aceeași alegere ca „Bogdan și Ana” — contează cine merge, nu în ce ordine i-ai numit. Câte perechi diferite poți forma? Exact 6 — și fiecare e o combinare: o submulțime în care ordinea nu are nicio importanță.
Intuiția
O combinare de k elemente din n este o submulțime de mărime k: alegi
k lucruri dintr-un grup de n, fără să-ți pese de ordine. Spre deosebire de
aranjamente, unde „12” și „21” sunt diferite, la combinări ele sunt una și
aceeași alegere. Numărul total de combinări se notează C(n,k).
Trucul pentru a le genera fără să te repeți: dacă alegi mereu elementele în ordine crescătoare a indicilor, fiecare submulțime apare exact o singură dată.
O submulțime are o singură scriere cu indici strict crescători. Dacă te legi
de regula „următorul element ales are mereu indice mai mare”, atunci {1,3} se
poate construi doar ca 13, niciodată ca 31. Astfel fiecare combinare se naște
exact o dată — fără nicio verificare de duplicate.