Calculator permutări și combinări

Folosiți permutări atunci când ordinea sau aranjarea elementelor selectate contează:

• atribuirea pozițiilor într-un clasament (locul 1, 2, 3)
• aranjarea cărților pe un raft
• crearea de parole sau coduri PIN
• organizarea locurilor la masă
• numere de telefon

Folosiți combinări atunci când doar alegeți o submulțime, iar ordinea este irelevantă:

• selectarea membrilor unei echipe
• alegerea numerelor la loto
• alegerea preparatelor din meniu
• formarea comitetelor

Un test simplu: dacă inversarea a două elemente selectate schimbă rezultatul, folosiți permutări; dacă inversarea nu schimbă nimic, folosiți combinări.

Numerele de la loto ilustrează perfect acest lucru — extragerea Mega Millions alege 5 numere din 70 plus 1 din 25: C(70,5) × 25 = 302.575.350 de variante posibile. Dacă ordinea ar fi contat, ar fi existat P(70,5) × 25 = 36.309.042.000 de posibilități — de 120 de ori mai multe.

Permutări simple: P(n,r) = n!/(n-r)!. P(10,3) = 10!/7! = 10×9×8 = 720.

Combinări simple: C(n,r) = n!/[r!(n-r)!]. C(10,3) = 10!/(3!×7!) = 720/6 = 120.

Cu repetare permisă: permutări = n^r (de exemplu, un PIN de 4 cifre din cifrele 0-9 are 10⁴ = 10.000 de posibilități).

Combinări cu repetare: C(n+r-1, r) — alegerea a 3 cupe din 5 arome de înghețată cu repetare permisă oferă C(7,3) = 35.

Pentru valori mari, folosiți formula multiplicativă pentru a evita calcularea factorialelor uriașe: C(52,5) = (52×51×50×49×48)/(5×4×3×2×1) = 2.598.960 — numărul de mâini posibile de 5 cărți la poker.

Securitatea parolelor: o parolă de 8 caractere ce folosește litere mari, litere mici, cifre și 10 simboluri (72 de caractere în total) are 72⁸ = 722 de trilioane de permutări cu repetare — ceea ce înseamnă că un atac prin forță brută ar dura aproximativ 22.800 de ani la o rată de 1 miliard de încercări pe secundă. Adăugarea a doar 2 caractere (o parolă de 10 caractere) crește numărul la 3,7 cvadrilioane — de 5.140 de ori mai greu de spart.

• În genetică, numărul de moduri de a alege 23 de perechi de cromozomi din cei 46 ai unui părinte este C(46,23) ≈ 8,2 miliarde, ceea ce explică diversitatea genetică.
• În controlul calității, selectarea a 5 produse dintr-un lot de 100 pentru testare implică C(100,5) = 75.287.520 de eșantioane posibile.
• În tablourile de turneu, numărul de tablouri posibile la NCAA March Madness este 2⁶³ ≈ 9,2 chintilioane — motiv pentru care nimeni nu a ghicit vreodată un tablou perfect.

O permutare este un aranjament ordonat de elemente, în timp ce o combinare este o selectare neordonată — această unică diferență, ordinea, explică totul.

Dacă alegeți literele A, B și C, aranjamentele ABC și CAB sunt două permutări diferite, dar aceeași combinare, deoarece combinările țin cont doar de ce elemente au fost alese, nu de secvența lor. După cum explică Encyclopaedia Britannica, combinatorica este ramura matematicii dedicată numărării acestor aranjamente și selectări.

Un test rapid: întrebați-vă dacă schimbarea locului a două elemente alese modifică rezultatul. Clasarea medaliaților cu aur, argint și bronz se schimbă dacă inversați doi alergători, deci ordinea contează și folosiți permutări. Alegerea a trei ingrediente pentru pizza nu se schimbă dacă le inversați ordinea, deci folosiți combinări.

Formula permutărilor este nPr = n! / (n − r)!, iar formula combinărilor este nCr = n! / [r! × (n − r)!], unde n! (n factorial) este produsul tuturor numerelor întregi de la 1 până la n.

Pentru a calcula P(10,3), se evaluează 10! / 7!, ceea ce se simplifică la 10 × 9 × 8 = 720. Pentru a calcula C(10,3), se împarte acel rezultat la 3! = 6, obținându-se 120. Factorialul crește rapid: 5! = 120 și 10! = 3.628.800.

Wolfram MathWorld definește coeficientul binomial C(n,r) exact în acest mod. Deoarece nCr elimină prin împărțire cele r! ordonări pe care permutările le numără separat, nCr este întotdeauna mai mic sau egal cu nPr pentru aceleași valori n și r.

Pentru a calcula C(52,5) — numărul de mâini de poker de cinci cărți — începeți cu forma multiplicativă în loc de factoriale complete, pentru a păstra numerele ușor de gestionat. Scrieți numărătorul ca fiind primii cinci factori descrescător, 52 × 51 × 50 × 49 × 48, iar numitorul ca fiind 5! = 120. Numărătorul este egal cu 311.875.200; împărțirea la 120 dă exact 2.598.960 de mâini posibile.

Pentru o verificare mai simplă, C(5,2) = (5 × 4) / (2 × 1) = 10, iar C(8,3) = (8 × 7 × 6) / (3 × 2 × 1) = 56.

Khan Academy predă această scurtătură de simplificare pentru că evită calcularea directă a factorialelor enorme. NIST Digital Library of Mathematical Functions (DLMF) oferă aceeași definiție pentru coeficientul binomial folosită aici.

Când repetarea este permisă, formulele se modifică deoarece elementele pot fi reutilizate.

• Pentru permutări cu repetare, numărul este pur și simplu n^r: un PIN de 4 cifre format din cifrele 0–9 are 10^4 = 10.000 de posibilități, deoarece fiecare dintre cele patru poziții are independent zece opțiuni.
• Pentru combinări cu repetare, numărul este C(n + r − 1, r). Alegerea a 3 cupe din 5 arome de înghețată atunci când repetările sunt permise oferă C(5 + 3 − 1, 3) = C(7,3) = 35.

Comparați acest lucru cu selectarea fără repetare, unde fiecare alegere reduce mulțimea cu un element. Repetarea crește dramatic totalul, motiv pentru care complexitatea parolelor și securitatea PIN-urilor se bazează pe ea — fiecare caracter adăugat multiplică posibilitățile.

Permutările și combinările apar oriunde se numără aranjamente sau selectări.

• Loterile folosesc combinări: alegerea a 6 numere din 49 oferă C(49,6) = 13.983.816 de variante posibile, stabilind șansele pentru marele premiu.
• Jocurile de cărți se bazează de asemenea pe ele — există 2.598.960 de mâini posibile de poker cu cinci cărți dintr-un pachet de 52 de cărți.
• Securitatea cibernetică folosește permutări cu repetare pentru a măsura câte parole sau chei sunt posibile, influențând direct rezistența la atacurile prin forță brută.
• Statistica și probabilitățile folosesc coeficientul binomial C(n,r) în cadrul distribuției binomiale și al triunghiului lui Pascal.
• Planificarea, stabilirea capiilor de serie în turnee, analiza secvențelor ADN și eșantionarea pentru controlul calității depind toate de aceste numărători.

Encyclopaedia Britannica notează că numărarea combinatorică stă la baza teoriei probabilităților, motiv pentru care acest calculator se potrivește în mod natural cu instrumentele de probabilitate și statistică.

Fiecare număr din triunghiul lui Pascal este un coeficient binomial nCr, astfel încât rezultatul combinărilor oferit de calculator este practic citirea unei valori din acel triunghi. Rândul 6 al triunghiului lui Pascal este 1, 6, 15, 20, 15, 6, 1 — exact C(6,0) până la C(6,6).

Aceste numere sunt coeficienții din dezvoltarea binomială (a + b)^n, motiv pentru care C(n,r) se numește coeficient binomial.

Două identități rezultă direct de aici:

• regula simetriei C(n,r) = C(n, n−r), deci C(15,4) = C(15,11) = 1.365
• regula sumei conform căreia toți coeficienții din rândul n adunați dau 2^n, deoarece C(4,0)+C(4,1)+C(4,2)+C(4,3)+C(4,4) = 1+4+6+4+1 = 16 = 2^4

Wolfram MathWorld și OEIS cataloghează triunghiul lui Pascal ca fiind secvența A007318.

• Cea mai frecventă eroare este alegerea instrumentului greșit: folosirea permutărilor atunci când ordinea nu contează mărește rezultatul cu un factor de r!, deoarece nPr numără fiecare grup neordonat de r! ori separat. De exemplu, tratarea unui comitet de 3 persoane din 10 ca fiind ordonat oferă P(10,3) = 720 în loc de valoarea corectă C(10,3) = 120.
• A doua greșeală este omiterea faptului că repetarea este permisă — un cod PIN reutilizează cifrele (n^r), dar extragerea la loto nu.
• A treia este confuzia dintre n și r, deoarece formulele nu sunt simetrice în raport cu acestea.
• În cele din urmă, evitați calcularea completă a factorialelor uriașe urmată de împărțire; folosiți metoda simplificării pentru ca valorile intermediare să rămână mici și să evitați erorile de depășire (overflow) sau de rotunjire.

Pentru orice valori fixe n și r, permutările sunt întotdeauna egale sau mai mari decât combinările, deoarece nPr = nCr × r!, factorul suplimentar reprezentând fiecare ordonare a elementelor alese.

Atunci când r = 1, acestea sunt egale, deoarece un singur element are o singură aranjare: P(20,1) = C(20,1) = 20. Pe măsură ce r crește, diferența se mărește rapid. Pentru n = 10 și r = 3, P(10,3) = 720, în timp ce C(10,3) = 120 — numărul de permutări este de exact 3! = 6 ori mai mare. Dacă alegem toate elementele, P(5,5) = 5! = 120, în timp ce C(5,5) = 1.

Acesta este motivul pentru care rezultatele ordonate cresc mult mai rapid ca număr decât selecțiile neordonate și de ce loteriile (combinările) au șanse mult mai bune decât ar avea dacă ordinea extragerii ar conta. Înțelegerea acestui raport te ajută să verifici rapid orice rezultat pe care îl returnează calculatorul.