Combinatorică — introducere

Combinatorica numără posibilități fără a le enumera una câte una. Mai întâi decizi dacă alegerile sunt alternative sau pași succesivi: vezi Principiile adunării și înmulțirii. Dacă folosești toate obiectele distincte și ordinea contează, problema duce la Permutări. Dacă alegi doar câteva și ordinea contează, mergi la Aranjamente; când ordinea nu contează, la Combinări. Coeficienții acestor alegeri apar în Binomul lui Newton.

Exemplu rezolvat. Câte coduri de două litere distincte se pot forma din A, B, C?

1. Pentru prima poziție alegem una dintre $3$ litere.
2. Pentru a doua rămân $2$.
3. Sunt $3\cdot 2=6$ coduri; ordinea contează, căci AB și BA diferă.

O problemă de numărare se clasifică prin trei întrebări: se folosesc toate obiectele sau doar o parte din ele? contează ordinea? se pot repeta obiectele? Răspunsurile indică modelul:

• toate cele $n$ obiecte, fără repetare, ordinea contează: permutări, $P_n=n!$;
• $k$ dintre cele $n$ obiecte, fără repetare, ordinea contează: aranjamente, $A_n^k=\frac{n!}{(n-k)!}$;
• $k$ dintre cele $n$ obiecte, fără repetare, ordinea nu contează: combinări, $C_n^k=\frac{n!}{k!(n-k)!}$;
• repetarea este permisă și ordinea contează: principiul produsului dă direct $n^k$ șiruri de lungime $k$ cu simboluri dintre cele $n$.

Aici $n!=1\cdot 2\cdots n$ și $0!=1$. Când un enunț are mai multe condiții, există trei căi de lucru: împarți în cazuri disjuncte și aduni; numeri tot și scazi cazurile interzise (metoda complementului); lipești obiectele care trebuie să stea alături într-un singur bloc. Enunțul indică ordinea prin cuvinte precum „cod”, „clasament”, „președinte și secretar”, „se așază”, iar lipsa ei prin „echipă”, „comisie”, „grup”, „submulțime”. Cuvântul „distincte” interzice repetarea.

Exemplu rezolvat. Un seif se deschide cu un cod de patru cifre. Câte coduri există dacă cifrele se pot repeta și câte dacă sunt distincte?

1. Cu repetare, fiecare poziție are $10$ cifre posibile: $10^4=10000$ coduri.
2. Fără repetare, ordinea contează și se folosesc $4$ din $10$ cifre: $A_{10}^4=10\cdot 9\cdot 8\cdot 7=5040$ coduri.
3. Diferența, $10000-5040=4960$, reprezintă codurile cu cel puțin o cifră repetată.

Exemplu rezolvat. Patru băieți și două fete se așază pe un rând. În câte moduri nu stau cele două fete alături?

1. Toate așezările: $P_6=6!=720$.
2. Cele două fete alăturate formează un bloc. Blocul și cei patru băieți dau $5!=120$ ordini, iar în bloc fetele se pot schimba între ele în $2!=2$ moduri: $120\cdot 2=240$ așezări.
3. Așezările cerute sunt $720-240=480$.

Exemplu rezolvat. La o competiție participă $12$ elevi. Ce model se aplică în fiecare dintre cele trei situații?

1. Clasamentul primilor trei (locurile I, II, III): $3$ dintre $12$, fără repetare, ordinea contează. Sunt aranjamente: $A_{12}^3=12\cdot 11\cdot 10=1320$.
2. Alegerea a trei delegați, fără roluri: ordinea nu contează. Sunt combinări: $C_{12}^3=\frac{12\cdot 11\cdot 10}{3!}=220$.
3. Ordinea de intrare în sală a tuturor celor $12$ elevi: sunt permutări, $12!=479001600$.

Exemplu rezolvat. Dintre cinci bărbați și patru femei se alege o comisie de trei persoane cu cel puțin o femeie. Numărăm prin complement: toate comisiile sunt $C_9^3=84$, cele formate numai din bărbați sunt $C_5^3=10$, deci rezultă $84-10=74$ de comisii. Pe cazuri, ar fi trebuit calculate separat comisiile cu una, două sau trei femei.

O mulțime cu $n$ elemente are $2^n$ submulțimi: pentru fiecare element se decide dacă intră sau nu în submulțime, iar cele $n$ decizii se înmulțesc. Pentru $n=5$ sunt $2^5=32$ de submulțimi, dintre care $C_5^2=10$ au exact două elemente.

Pentru două mulțimi finite, $|A\cup B|=|A|+|B|-|A\cap B|$: elementele comune se scad o singură dată, fiindcă au fost adunate de două ori. La numărările de forma „cel puțin unul” este adesea mai scurt complementul: se scade din total ceea ce nu îndeplinește condiția.

Problemă. Câte numere naturale de la $1$ la $100$ nu sunt divizibile nici cu $2$, nici cu $5$?

• a) $20$
• b) $30$
• c) $40$
• d) $50$
• e) $60$
• f) $70$

Rezolvare. Multiplii lui $2$ sunt $50$, ai lui $5$ sunt $20$, iar ai lui $10$ (divizibili cu ambele) sunt $10$. Numerele divizibile cu $2$ sau cu $5$ sunt $50+20-10=60$. Rămân $100-60=40$. Răspunsul corect este c). Varianta a) apare dacă se scade și intersecția: $100-50-20-10=20$. Varianta b) rezultă din $100-(50+20)=30$, adică intersecția nu se adaugă la loc. Varianta d) numără doar numerele impare, fără să elimine multiplii lui $5$. Varianta e) este numărul celor care au cel puțin una dintre proprietăți, nu al celor care nu au niciuna. Varianta f) este suma $50+20$.

Alt exemplu. Câte numere de trei cifre conțin cel puțin o cifră $7$? Toate numerele de trei cifre sunt $900$. Fără cifra $7$: prima cifră are $8$ variante (nu $0$, nu $7$), iar celelalte două câte $9$, deci $8\cdot 9\cdot 9=648$. Rezultă $900-648=252$. Pe cazuri, același total cere trei numărări: exact un $7$ (în sute: $9\cdot 9=81$; în zeci sau în unități: $8\cdot 9=72$ fiecare, deci $225$), exact doi de $7$ ($9+9+8=26$) și trei de $7$ ($1$), adică $225+26+1=252$. Complementul cere o singură înmulțire.

Greșeli frecvente

• Greșit: codurile de patru cifre distincte ale unui seif sunt $10^4=10000$.
  Corect: cifrele nu se repetă, deci sunt $10\cdot 9\cdot 8\cdot 7=5040$ coduri.
• Greșit: dintre $3$ elevi, alegerea unui președinte și a unui secretar se numără prin $C_3^2=3$.
  Corect: funcțiile sunt diferite, deci sunt $A_3^2=3\cdot 2=6$ posibilități.
• Greșit: șase persoane se așază pe un rând, cu două anume nealăturate, în $6!-5!=600$ de moduri.
  Corect: perechea alăturată se poate așeza în două ordini, deci se scad $2\cdot 5!$ cazuri: $720-240=480$.
• Greșit: o mulțime cu $5$ elemente are $5^2=25$ de submulțimi.
  Corect: fiecare element este ales sau nu, deci sunt $2^5=32$.

Înainte și după

Întrebări frecvente