Elemente de calcul combinatorial

Studiul permutărilor, aranjamentelor și combinărilor cu aplicații în probabilitate.

Permutări și factorialul

O permutare a unei mulțimi cu n elemente este o ordonare a tuturor celor n elemente. Numărul permutărilor este Pₙ = n! (n factorial), unde n! = 1 · 2 · 3 · ... · n, cu convenția fundamentală 0! = 1.

De ce n!? Gândește pe locuri: pentru primul loc ai n opțiuni, pentru al doilea rămân n − 1, pentru al treilea n − 2 și așa mai departe — se aplică regula produsului: numărul total de variante este produsul numerelor de opțiuni de la fiecare pas.

Exemplu: 5 cărți diferite se pot așeza pe un raft în 5! = 120 de moduri.

Calculul cu factoriale apare des la simplificări: n!/(n−2)! = n(n−1), pentru că toți factorii până la (n−2)! se simplifică. Nu calcula niciodată factorialele mari complet — simplifică întâi fracția.

Atenție la o eroare frecventă: n! crește extrem de repede (10! este deja peste 3,6 milioane), deci un rezultat de tip „număr mic” după un calcul cu factoriale mari e un semnal că s-a simplificat ceva, nu că s-a greșit. Verifică ecuațiile cu factoriale (de exemplu n! = 720 dă n = 6) prin încercare directă cu valori mici.

Aranjamente

Un aranjament de n luate câte k este o alegere ordonată de k elemente distincte dintr-o mulțime cu n elemente. Numărul lor este:

Aₙᵏ = n!/(n−k)! = n(n−1)(n−2)...(n−k+1) — un produs de exact k factori descrescători, începând de la n.

Exemplu: câte numere de 3 cifre distincte se pot forma cu cifrele 1, 2, 3, 4, 5? Răspuns: A₅³ = 5 · 4 · 3 = 60 — contează și ce cifre alegi, și în ce ordine le așezi.

Cazuri particulare de reținut: Aₙⁿ = n! (aranjamentele tuturor elementelor sunt chiar permutările) și Aₙ¹ = n.

Cum recunoști aranjamentele în enunț: apar cuvinte care implică ordine sau roluri diferite — „podium” (locul 1 diferă de locul 2), „președinte și vicepreședinte”, „cod format din cifre distincte”, „steag din benzi colorate”. Dacă schimbarea ordinii elementelor alese produce o situație diferită, folosești aranjamente.

Condiția de existență: 0 ≤ k ≤ n. La ecuațiile cu aranjamente (de exemplu Aₙ² = 42), scrie produsul desfășurat n(n−1) = 42 și rezolvă, dar păstrează doar soluțiile naturale care respectă condițiile de existență — soluția negativă se elimină obligatoriu, cu justificare.

Combinări

O combinare de n luate câte k este o alegere de k elemente dintr-o mulțime cu n elemente, în care ordinea nu contează — alegem o submulțime. Numărul lor este:

Cₙᵏ = n!/(k!(n−k)!) = Aₙᵏ/k!

Împărțirea la k! elimină exact ordonările interne: fiecare submulțime de k elemente fusese numărată de k! ori printre aranjamente.

Proprietăți esențiale la examen:

• Formula combinărilor complementare: Cₙᵏ = Cₙⁿ⁻ᵏ (a alege k elemente înseamnă a lăsa deoparte n−k);
• Formula de recurență (regula lui Pascal): Cₙᵏ = Cₙ₋₁ᵏ⁻¹ + Cₙ₋₁ᵏ;
• Valori particulare: Cₙ⁰ = Cₙⁿ = 1, Cₙ¹ = n;
• Suma tuturor combinărilor: Cₙ⁰ + Cₙ¹ + ... + Cₙⁿ = 2ⁿ — numărul total de submulțimi ale unei mulțimi cu n elemente.

Cum recunoști combinările în enunț: „echipă”, „comisie”, „delegație”, „grup”, „câte submulțimi” — situații în care membrii aleși au același rol, deci ordinea alegerii nu schimbă rezultatul.

Testul decisiv aranjament versus combinare: întreabă-te dacă schimbând între ele două elemente alese obții o situație nouă. Da → aranjamente. Nu → combinări.

Triunghiul lui Pascal și binomul lui Newton

Triunghiul lui Pascal aranjează combinările Cₙᵏ pe linii: linia n conține Cₙ⁰, Cₙ¹, ..., Cₙⁿ. Fiecare element interior este suma celor doi vecini de deasupra — exact regula lui Pascal Cₙᵏ = Cₙ₋₁ᵏ⁻¹ + Cₙ₋₁ᵏ. Triunghiul este simetric, reflectând formula combinărilor complementare.

Binomul lui Newton dă dezvoltarea puterii unui binom:

(a + b)ⁿ = Cₙ⁰aⁿ + Cₙ¹aⁿ⁻¹b + Cₙ²aⁿ⁻²b² + ... + Cₙⁿbⁿ

Termenul general — formula care rezolvă majoritatea cerințelor de examen — este:

Tₖ₊₁ = Cₙᵏ aⁿ⁻ᵏ bᵏ, pentru k = 0, 1, ..., n.

Detalii care fac diferența la punctaj:

• Dezvoltarea are n + 1 termeni, nu n;
• Indicele termenului este k + 1, dar exponentul lui b este k: termenul al patrulea corespunde lui k = 3 — decalajul acesta pierde constant puncte;
• Pentru (a − b)ⁿ, semnele alternează: termenul general capătă factorul (−1)ᵏ;
• Suma coeficienților binomiali Cₙ⁰ + ... + Cₙⁿ = 2ⁿ se obține punând a = b = 1; suma alternată este 0 (a = 1, b = −1).

Cerință tipică: găsirea termenului care conține o anumită putere a lui x. Scrii termenul general, aduni exponenții lui x și impui condiția cerută — rezultă k.

Aplicații și strategii de numărare

Problemele de numărare de la examen se rezolvă combinând două principii de bază:

• Regula produsului: dacă o acțiune se face în etape succesive, iar etapele au m, respectiv n variante independente, atunci în total sunt m · n variante;
• Regula sumei: dacă situațiile se împart în cazuri disjuncte (care nu se pot întâmpla simultan), numărul total este suma numerelor pe cazuri.

Strategii verificate:

• Formarea numerelor cu cifre: prima cifră nu poate fi 0 — tratează primul loc separat. Câte numere de 3 cifre distincte există cu cifrele 0-9? Prima cifră: 9 opțiuni (fără 0), apoi 9 și 8: în total 9 · 9 · 8 = 648;
• Cel puțin unul: adesea e mai simplu prin complementară — numeri totalul și scazi cazurile cu „niciunul”;
• Comitete cu structură (de exemplu 2 fete din 6 și 3 băieți din 8): combinări pe fiecare categorie, apoi produsul lor: C₆² · C₈³;
• Obiecte care stau obligatoriu împreună: „lipești” grupul într-un singur obiect, permuți, apoi înmulțești cu permutările interne ale grupului.

După orice numărare, fă testul de plauzibilitate: rezultatul trebuie să fie număr natural, iar la combinări nu poate depăși 2ⁿ. Un rezultat fracționar înseamnă aproape sigur că ai împărțit la k! unde nu trebuia sau ai uitat o simplificare.

Test — 6 întrebări ca la examen