Combinări

Folosim combinările atunci când alegem dintr-o mulțime de obiecte un anumit număr de obiecte și nu contează ordinea în care le alegem. O problemă tipică este Loto 6/49 – într-o urnă avem 49 de numere și extragem 6 dintre ele, iar ordinea în care le extragem nu are importanță.

Deducerea formulei

Fie o mulțime M, de exemplu M = {a, b, c, d, e}. Atunci o combinare de k elemente este o submulțime K ⊆ M care conține exact k elemente. Deoarece K este o mulțime, evident că ordinea nu contează. O combinare de trei elemente din mulțimea M ar putea fi deci {a, b, d} sau {b, c, d}.

Diferența față de aranjamente este că la aranjamente ordinea conta, deci (a, b, e) și (e, b, a) sunt aranjamente diferite, dar sunt aceeași combinare, pentru că și (a, b, e), și (e, b, a) conțin aceleași elemente; faptul că sunt în altă ordine nu ne interesează la combinări.

Putem totuși folosi aranjamentele pentru a obține formula numărului tuturor combinărilor diferite. Știm că numărul aranjamentelor de k elemente dintr-o mulțime cu n elemente este exact

$$A_n^k=\frac{n!}{(n-k)!}.$$

Dacă am calcula deci numărul tuturor aranjamentelor de trei elemente din mulțimea anterioară M = {a, b, c, d, e}, am obține $A_5^3=60$ de aranjamente diferite. Însă acolo am avea pentru fiecare triplet și toate permutările lui. Adică am avea tripletul abc, dar și tripletele acb, bac, bca, cab și cba. Acestea sunt șase aranjamente diferite, dar o singură combinare, pentru că toate au aceleași elemente.

Dacă avem deci un triplet, câte permutări diferite ale acestui triplet există? Exact 3!. Cu alte cuvinte, există de exact 3! ori mai multe aranjamente de trei elemente decât combinări de trei elemente. În loc să numărăm o singură combinare, numărăm de 3! ori mai multe aranjamente, câte unul pentru fiecare permutare a tripletului dat. Deci, dacă împărțim numărul aranjamentelor la 3!, obținem numărul combinărilor.

Putem generaliza procedeul de mai sus și putem spune că, dacă ne interesează numărul tuturor combinărilor diferite de k elemente dintr-o mulțime cu n elemente, atunci acest număr, notat $C_n^k$, este egal cu

$$C_n^k=\frac{A_n^k}{k!},$$

adică numărul aranjamentelor împărțit la k!, care este numărul permutărilor fiecărui k-uplu. Formula o putem transforma dezvoltând formula de calcul a aranjamentelor:

$$C_n^k=\frac{A_n^k}{k!}=\frac{n!}{(n-k)!}\cdot \frac{1}{k!}=\frac{n!}{(n-k)!\cdot k!}.$$

Exemplu: numărul combinărilor de două elemente din mulțimea {a, b, c} este

$$C_3^2=\frac{3!}{1!\cdot 2!}=3$$

iar combinările sunt: {a, b}, {a, c} și {b, c}. Pentru combinările de trei elemente din mulțimea inițială M = {a, b, c, d, e} am obține numărul

$$C_5^3=\frac{5!}{(5-3)!\cdot 3!}=10$$

iar combinările sunt: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Numărul combinărilor

Numărul combinărilor $C_n^k$ se citește „combinări de n luate câte k”. Formula lui o cunoști deja:

$$C_n^k=\frac{n!}{(n-k)!\cdot k!}$$

Deci, dacă avem o mulțime cu 5 elemente și alegem din ea grupe de câte patru elemente, numărul lor total va fi

$$C_5^4=\frac{5!}{1!\cdot 4!}=5.$$

Relații de bază

Pentru n ∈ ℕ^∗ avem:

$$\begin{array}{rcl}{C}_n^0=C_n^n=C_0^0& =& 1\\ C_n^1& =& n\end{array}$$

Mai departe, pentru n, k ∈ ℕ și k ≤ n avem

$$\begin{array}{rcl}{C}_n^{n-k}& =& C_n^k.\end{array}$$

Iar pentru n, k ∈ ℕ și k < n avem

$$\begin{array}{rcl}{C}_n^k+C_n^{k+1}& =& C_{n+1}^{k+1}.\end{array}$$

Calculator

Următorul calculator îți calculează numărul de combinări $C_n^k$.

Exemple rezolvate

1. Începem cu Loto 6/49, amintit deja. La el se extrag dintr-o urnă în care sunt 49 de bile în total 6 bile. Câte rezultate diferite pot fi extrase?

   Înainte de toate – contează ordinea extragerii numerelor? Nu contează, pariem doar pe numere, nu pe ordinea lor. Vom folosi combinări. Avem în total 49 de bile, extragem 6 bile, obținem

   $$C_{49}^6=\frac{49!}{(49-6)!\cdot 6!}=\frac{49!}{43!\cdot 6!}=13.983.816$$

   Există în total 13.983.816 de rezultate care pot fi extrase. Ceea ce ne dă, apropo, probabilitatea de câștig cu o singură variantă jucată $\frac{1}{13.983.816}$, adică 0,00000715112%.

2. Radu, un mare cuceritor, se află chiar la o petrecere a satului, unde sunt în total 13 fete frumoase care i-ar plăcea. Radu știe că este în stare să facă fericite într-o seară 4 fete diferite. Dintre câte grupe de câte patru poate Radu să aleagă?

   Este din nou un exemplu simplu de combinări, ordinea nu contează, Radu va fi la fel de bun cu prima fată ca și cu ultima. Obținem deci o mulțime de 13 fete, din care alegem de fiecare dată câte 4. Aceasta duce la

   $$C_{13}^4=715.$$

3. Ai un grup de cincizeci de persoane – jumătate bărbați și jumătate femei. Câte triplete diferite de persoane există, dacă nu pot fi formate din persoane de un singur sex (adică în triplet nu pot apărea trei bărbați sau trei femei)?

   Aceasta este deja o combinare ceva mai complicată. Dacă excludem tripletele de același sex, ne rămân doar două posibilități de a forma tripletul – doi bărbați și o femeie sau un bărbat și două femei, iar numărul combinărilor primului grup (doi bărbați și o femeie) va fi același cu numărul combinărilor celui de-al doilea grup. Este deci suficient să calculăm numărul combinărilor primului grup și să-l înmulțim apoi cu doi. Acum e din nou floare la ureche. Determinăm numărul combinărilor de perechi diferite de bărbați, adică $C_{25}^2$, și înmulțim cu numărul combinărilor unei singure femei (acesta este douăzeci și cinci, vezi relațiile de bază de mai sus, anume a doua linie). Acest rezultat îl mai înmulțim doar cu doi și avem rezultatul final.

   $$2\cdot C_{25}^2\cdot C_{25}^1=15.000.$$

4. Într-o cutie sunt 15 produse, dintre care 4 sunt defecte. În câte moduri se pot alege 6 produse astfel încât

   • niciunul să nu fie defect? Acum alegem 6 produse dintre cele 15 − 4 = 11 produse care nu sunt defecte. Obținem deci

     $$C_{11}^6=462.$$

   • exact un produs să fie defect? Alegem deci o mulțime care conține 5 produse bune și 1 defect. Produse bune avem în total 11, defecte avem 4. Folosim regula produsului și obținem rezultatul:

     $$C_{11}^5\cdot C_4^1=1848$$

   • cel mult un produs să fie defect? Pentru rezolvare folosim rezultatele anterioare. Știm că avem în total 462 de posibilități de a alege exact 6 produse bune și avem 1848 de posibilități de a alege cinci produse bune și un produs defect. Folosim deci regula sumei, adunăm aceste rezultate și avem rezultatul pe care îl căutăm, adică cel mult un produs defect (= fie niciun produs defect, fie exact unul). Rezultatul este deci: 462 + 1848 = 2310.

Surse și lecturi suplimentare

• Bělohlávek, Vychodil: Diskrétní matematika (în limba cehă)