Combinatorică

Vrei să știi câte grupe diferite de cinci cărți poți alege dintr-un pachet de 32 de cărți de joc? Exact acesta este tipul de problemă pe care o rezolvă combinatorica. Există două reguli combinatorice de bază – regula sumei și regula produsului. Toate celelalte metode sunt doar extinderi ale acestor principii.

Regula sumei

Regula sumei este foarte simplă – ne spune că, dacă avem mulțimile A, B care nu au niciun element comun, atunci numărul tuturor modurilor posibile de a alege un element din reuniunea A ∪ B este egal cu |A| + |B|, adică cu suma cardinalelor mulțimilor.

Începem cu un exemplu ușor. Avem 6 bile roșii și 8 bile albastre. Punem bilele într-o urnă. Câte posibilități avem în total dacă extragem o singură bilă? La început aveam mulțimea bilelor roșii, pe care o notăm cu A, apoi mulțimea bilelor albastre, notată B. Aceste mulțimi sunt disjuncte, adică nu au nicio bilă în comun. Vrem să extragem o singură bilă, deci avem în total |A| + |B| = 6 + 8 = 14 posibilități. Atât.

Regula produsului

Avem din nou două mulțimi, F și B. Mulțimea F conține trei fete, iar mulțimea B patru băieți. Ne întrebăm acum câte perechi diferite „fată – băiat” putem forma din aceste mulțimi. Ce încercăm să facem – luăm de fiecare dată o fată și îi alăturăm un băiat. Numărul tuturor perechilor îl aflăm astfel: luăm o fată, pe Ana, și îi alăturăm pe rând toți băieții. Obținem 4 perechi diferite, pentru că ei îi putem alătura în total 4 băieți diferiți. Același lucru îl facem pentru celelalte două fete, iar și ele formează de fiecare dată câte 4 perechi. Și asta e tot, avem în total 4 + 4 + 4 = 12 perechi.

Ce am făcut, de fapt? Am înmulțit cardinalele celor două mulțimi. Aveam 3 fete și 4 băieți, deci numărul total de perechi este 3 · 4 = 12. De aici și numele de regula produsului. Dacă avem deci două mulțimi din care formăm perechi, pur și simplu înmulțim numărul de elemente ale primei mulțimi cu numărul de elemente ale celei de-a doua.

Poți vedea mai jos că așa este într-adevăr. Urmează toate perechile care se pot forma cu 3 fete și 4 băieți. Fiecare linie reprezintă posibilitățile pentru una dintre fete, iar fiecare coloană posibilitățile pentru unul dintre băieți. Avem deci trei linii și patru coloane, în total linii · coloane posibilități.

$$\begin{array}{rcl}& & (F_1,B_1),(F_1,B_2),(F_1,B_3),(F_1,B_4),\\ & & (F_2,B_1),(F_2,B_2),(F_2,B_3),(F_2,B_4),\\ & & (F_3,B_1),(F_3,B_2),(F_3,B_3),(F_3,B_4)\end{array}$$

Exemple rezolvate

1. Câte numere de două cifre există? Cum arată un astfel de număr? Pe primul loc se află una dintre cifrele 1, …, 9, în timp ce pe al doilea loc poate apărea în plus și zero: 0, …, 9. În prima mulțime avem deci 9 cifre, în a doua 10. Folosim regula produsului și obținem rezultatul final: 9 · 10 = 90.

• Câte numere de trei cifre există, în care nicio cifră nu apare de două ori? Pe primul loc pot fi din nou nouă cifre, deoarece numărul nu poate începe cu zero. Pe al doilea loc pot fi toate cifrele, inclusiv zero, dar nu poate fi cifra de pe prima poziție, așa că din cele zece cifre posibile scădem una (de exemplu, dacă numărul nostru de trei cifre începe cu 4, este clar că pe a doua poziție nu mai poate apărea 4, pentru că ar apărea de două ori în număr). Pe al treilea loc pot fi din nou toate cifrele, dar nu poate fi nicio cifră aflată pe prima sau pe a doua poziție. Motivul este același. Dacă pe primul loc este cifra 4 și pe al doilea cifra 7, atunci pe al treilea loc putem pune o cifră din {0, …, 9} ∖ {4, 7}. Din cele zece cifre trebuie deci să scădem două. Acum nu ne mai rămâne decât să înmulțim: 9 · 9 · 8 = 648. În total există deci 648 de astfel de numere.
• Aruncăm de două ori la rând un zar obișnuit. Câte rezultate diferite putem obține? La prima aruncare pot ieși 6 rezultate diferite. La a doua la fel, deci numărul total de posibilități este 6 · 6 = 36.
• Aruncăm de două ori un zar. Câte rezultate diferite putem obține dacă la prima aruncare a ieșit un număr par? La prima aruncare a ieșit un număr par, adică unul dintre numerele 2, 4, 6, deci 3 posibilități. La a doua aruncare poate ieși orice număr, așadar avem în total 3 · 6 = 18 posibilități.

Surse și lecturi suplimentare

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