Combinări

O combinare de $n$ obiecte distincte luate câte $k$ este o alegere în care ordinea nu contează. Numărul este $C_n^k=\frac{n!}{k!(n-k)!}$, pentru $0\le k\le n$. Fiecare grup de $k$ obiecte apare de $k!$ ori printre aranjamente, de unde împărțirea prin $k!$.

Exemplu rezolvat. Alegi o echipă de doi elevi din cinci.

1. Alegerea ordonată ar da $5\cdot 4=20$ perechi.
2. Fiecare echipă apare de două ori: AB și BA.
3. Împărțim la $2!=2$ și obținem $C_5^2=10$ echipe.

Un număr $C_n^k$ este numărul submulțimilor cu $k$ elemente ale unei mulțimi cu $n$ elemente. Numerele $C_n^k$ se numesc și coeficienți binomiali, fiindcă sunt coeficienții termenilor din dezvoltarea lui $(a+b{)}^n$; lecția „Binomul lui Newton” o tratează. Valorile extreme sunt $C_n^0=C_n^n=1$ (submulțimea vidă, respectiv mulțimea întreagă) și $C_n^1=n$. Proprietatea de simetrie este $C_n^k=C_n^{n-k}$: alegerea celor $k$ membri echivalează cu alegerea celor $n-k$ rămași afară. Relația lui Pascal este $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$, deoarece un obiect fix este fie ales, fie neales: dacă este ales, se mai aleg $k-1$ din celelalte $n-1$; dacă nu, se aleg $k$ din cele $n-1$. Numărul tuturor submulțimilor este $C_n^0+C_n^1+\cdots +C_n^n=2^n$. Relația lui Pascal se citește în triunghiul lui Pascal: în rândul $n=5$, adică $1;5;10;10;5;1$, suma $10+10=20$ este numărul $C_6^3$ din rândul următor.

Pentru calcul, se scriu $k$ factori descrescători începând cu $n$ și se împarte la $k!$: $C_{10}^3=\frac{10\cdot 9\cdot 8}{3\cdot 2\cdot 1}=120$. Din simetrie rezultă și o regulă pentru ecuații: dacă $C_n^a=C_n^b$ cu $a\ne b$, atunci $a+b=n$. De exemplu, $C_n^3=C_n^5$ dă $n=8$, iar verificarea este $C_8^3=C_8^5=56$.

Exemplu rezolvat. Calculează $C_6^4$.

1. Prin simetrie, $C_6^4=C_6^2$.
2. $C_6^2=\frac{6\cdot 5}{2}=15$.
3. Rezultatul este $15$.

Dacă alegem pe categorii independente, folosim produsul numerelor de alegeri din fiecare categorie. Exemplu rezolvat. Din trei fete și doi băieți alegem o echipă de trei cu exact două fete. Alegerea fetelor are $C_3^2=3$ variante, alegerea băiatului $C_2^1=2$ variante. Numărul echipelor este $3\cdot 2=6$. Nu înmulțim cu $3!$, fiindcă ordinea persoanelor în aceeași echipă nu creează o altă echipă.

Exemplu rezolvat. Dintr-un grup de $8$ elevi, între care Ana, se alege o echipă de $3$ elevi. Câte echipe conțin pe Ana și câte nu?

1. Toate echipele: $C_8^3=\frac{8\cdot 7\cdot 6}{3!}=56$.
2. Echipele cu Ana: Ana este deja aleasă, deci se mai aleg $2$ elevi dintre ceilalți $7$: $C_7^2=21$.
3. Echipele fără Ana: se aleg $3$ elevi dintre cei $7$: $C_7^3=35$.
4. Cele două categorii sunt disjuncte și $21+35=56$, adică exact relația lui Pascal $C_8^3=C_7^2+C_7^3$.

Exemplu rezolvat. Câte submulțimi cu cel puțin $2$ elemente are mulțimea $\{1;2;3;4;5\}$?

1. Toate submulțimile sunt $2^5=32$.
2. Submulțimea vidă este $C_5^0=1$, iar cele cu un singur element sunt $C_5^1=5$.
3. Cele cerute sunt $32-1-5=26$.

Exemplu rezolvat. În plan se dau $7$ puncte, dintre care $4$ sunt coliniare, iar oricare alte trei nu sunt coliniare. Câte triunghiuri și câte drepte determină ele?

1. Orice $3$ puncte determină un triunghi, cu excepția celor $3$ coliniare. Triplete de puncte: $C_7^3=35$; triplete coliniare: $C_4^3=4$. Triunghiurile sunt $35-4=31$.
2. Orice $2$ puncte determină o dreaptă: $C_7^2=21$ perechi. Cele $C_4^2=6$ perechi formate din punctele coliniare dau toate aceeași dreaptă, numărată de $6$ ori în loc de o dată.
3. Dreptele sunt $21-6+1=16$.

Exemplu rezolvat. Rezolvă ecuația $C_n^2=21$.

1. Condiția de existență: $n\in \mathbb{N}$, $n\ge 2$.
2. $\frac{n(n-1)}{2}=21$, deci $n^2-n-42=0$, cu rădăcinile $n=7$ și $n=-6$.
3. Convine numai $n=7$. Verificare: $C_7^2=\frac{7\cdot 6}{2}=21$.

Combinările fără repetiție numără submulțimi, fără ordine: $C_n^k=n!/[k!(n-k)!]$. La grilă, simetria $C_n^k=C_n^{n-k}$ scurtează calculul (de exemplu $C_{10}^8=C_{10}^2=45$), iar pentru „cel puțin” complementul este adesea mai scurt. Dacă enunțul impune structura alegerii („exact doi băieți”, „trei dintr-o grupă și doi din alta”), se înmulțesc numerele de combinări ale grupelor; dacă enunțul listează cazuri care se exclud, se adună. La varianta cu șase răspunsuri, un test rapid este ordinul de mărime: de exemplu, numărul diagonalelor unui poligon trebuie să fie mai mic decât numărul tuturor segmentelor dintre vârfuri.

Problemă. Câte diagonale are un poligon convex cu $10$ laturi?

• a) $7$
• b) $35$
• c) $45$
• d) $70$
• e) $90$
• f) $100$

Rezolvare. Orice două vârfuri determină un segment: $C_{10}^2=45$ segmente. Dintre ele, $10$ sunt laturi, iar celelalte sunt diagonale: $45-10=35$. Răspunsul corect este b). Verificare cu formula $\frac{n(n-3)}{2}$: din fiecare vârf pleacă $n-3=7$ diagonale, iar produsul $10\cdot 7=70$ numără fiecare diagonală de două ori, deci $70/2=35$. Varianta a) este numărul diagonalelor dintr-un singur vârf. Varianta c) numără toate segmentele, inclusiv laturile. Varianta d) nu împarte la $2$ și numără fiecare diagonală de două ori. Varianta e) este $A_{10}^2=90$, adică ține cont de ordinea capetelor. Varianta f) este $10^2$, produsul dintre numărul de vârfuri și el însuși.

Alt exemplu. O comisie de $5$ persoane se alege dintre $6$ femei și $4$ bărbați, cu cel puțin $2$ bărbați. Toate comisiile: $C_{10}^5=252$. Fără bărbați: $C_6^5=6$. Cu exact un bărbat: $C_4^1{C}_6^4=4\cdot 15=60$. Comisiile cerute sunt $252-6-60=186$.

Greșeli frecvente

• Greșit: echipa AB diferă de echipa BA.
  Corect: într-o combinare sunt aceeași alegere.
• Greșit: $C_n^k=A_n^k$.
  Corect: $C_n^k=A_n^k/k!$; de exemplu $C_5^2=10$, dar $A_5^2=20$.
• Greșit: formula se folosește pentru $k>n$ fără convenție.
  Corect: în numărarea alegerilor cerem $0\le k\le n$.
• Greșit: într-un poligon convex cu $10$ laturi sunt $C_{10}^2=45$ diagonale.
  Corect: $C_{10}^2$ numără toate segmentele dintre vârfuri, inclusiv cele $10$ laturi; diagonalele sunt $45-10=35$.

Înainte și după

Întrebări frecvente