Numărul de combinații k dintr-un anumit ansamblu S cu n elemente este adesea notat în textele de combinatorică elementară prin C ( n , k ) {\displaystyle C(n,k)}.
, sau printr-o variație cum ar fi C k n {\displaystyle C_{k}^{n}}
, n C k {\displaystyle {}_{n}C_{k}}}.
, n C k {\displaystyle {\displaystyle {}^{n}C_{k}}}
, C n , k {\displaystyle C_{n,k}}
sau chiar C n k {\displaystyle C_{n}^{k}}}.
(această din urmă formă a fost standard în textele franceze, românești, rusești, chinezești și poloneze). Același număr apare însă în multe alte contexte matematice, unde este notat cu ( n k ) {\displaystyle {\tbinom {n}{k}}}}.
(adesea citit ca „n alege k”); în special apare ca un coeficient în formula binomială, de unde și numele său de coeficient binomial. Se poate defini ( n k ) {\displaystyle {\tbinom {n}{k}}}}
pentru toate numerele naturale k deodată prin relația ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}}X^{k}},}
din care este clar că
( n 0 ) = ( n n ) = 1 , {\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}
și, mai departe,
( n k ) = 0 {\displaystyle {\binom {n}{k}}=0}
pentru k > n.
Pentru a vedea că acești coeficienți numără k-combinări din S, se poate considera mai întâi o colecție de n variabile distincte Xs etichetate de elementele s din S și se poate extinde produsul peste toate elementele lui S:
∏ ∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s});}
are 2n termeni distinși care corespund tuturor subansamblurilor lui S, fiecare subansamblu dând produsul variabilelor Xs corespunzătoare. Acum, stabilind toate Xs egale cu variabila neetichetată X, astfel încât produsul să devină (1 + X)n, termenul pentru fiecare combinație k din S devine Xk, astfel încât coeficientul acelei puteri din rezultat este egal cu numărul de astfel de combinații k.
Coreficienții binomiali pot fi calculați explicit în diverse moduri. Pentru a-i obține pe toți pentru dezvoltările până la (1 + X)n, se poate folosi (în plus față de cazurile de bază deja prezentate) relația de recursivitate
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}
pentru 0 < k < n, ceea ce rezultă din (1 + X)n = (1 + X)n – 1(1 + X); aceasta conduce la construcția triunghiului lui Pascal.
Pentru determinarea unui coeficient binomial individual, este mai practic să se folosească formula
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k ! {\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}}
.
Numeratorul dă numărul de k-permutații ale lui n, adică, de secvențe de k elemente distincte ale lui S, în timp ce numitorul dă numărul de astfel de k-permutații care dau aceeași k-combinație atunci când se ignoră ordinea.
Când k depășește n/2, formula de mai sus conține factori comuni numărătorului și numitorului, iar anularea lor dă relația
( n k ) = ( n n – k ) , {\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},}
pentru 0 ≤ k ≤ n. Aceasta exprimă o simetrie care este evidentă din formula binomială și poate fi înțeleasă, de asemenea, în termeni de combinații k, luând complementul unei astfel de combinații, care este o combinație (n – k)-combinație.
În sfârșit, există o formulă care prezintă direct această simetrie și are meritul de a fi ușor de reținut:
( n k ) = n ! k ! ( n – k ) ! , {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}
unde n! reprezintă factorialul lui n. Se obține din formula anterioară prin înmulțirea numitorului și numitorului cu (n – k)!, deci este cu siguranță mai puțin eficientă din punct de vedere computațional decât acea formulă.
Ultima formulă poate fi înțeleasă direct, considerând cele n! permutări ale tuturor elementelor lui S. Fiecare astfel de permutare dă o combinație k prin selectarea primelor k elemente ale acesteia. Există multe selecții duplicate: orice permutare combinată a primelor k elemente între ele și a ultimelor (n – k) elemente între ele produce aceeași combinație; astfel se explică diviziunea din formulă.
Din formulele de mai sus rezultă relațiile dintre numerele adiacente din triunghiul lui Pascal în toate cele trei direcții:
( n k ) = { ( n k – 1 ) n – k + 1 k dacă k > 0 ( n – 1 k ) n n – k dacă k < n ( n – 1 k – 1 ) n k dacă n , k > 0 {\displaystyle {\binom {n}{k}}}={\begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quadru {\text{if }}k>0\\\{\binom {n-1}{k}}}{\frac {n}{n-k}}}&\quad {\text{if }}k<n\\\{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}}
.
Împreună cu cazurile de bază ( n 0 ) = 1 = ( n n ) {\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}}.
, acestea permit calculul succesiv al tuturor numerelor de combinații din același set (o linie în triunghiul lui Pascal), al combinațiilor k de seturi de mărimi crescânde și al combinațiilor cu un complement de mărime fixă n – k.
Exemplu de numărare a combinațiilorEdit
Ca un exemplu specific, se poate calcula numărul de mâini de cinci cărți posibile dintr-un pachet standard de cincizeci și două de cărți astfel:
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311.875.200 120 = 2.598.960. {\displaystyle {52 \alege 5}={\frac {52\timpuri 51\timpuri 50\timpuri 49\timpuri 48}{5\timpuri 4\timpuri 3\timpuri 2\timpuri 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}
În mod alternativ se poate folosi formula în termeni factoriali și se pot anula factorii de la numărător cu părți din factorii de la numitor, după care este necesară doar înmulțirea factorilor rămași:
( 52 5 ) = 52 ! 5 ! 47 ! = 52 × 51 × 50 × 49 × 48 × 47 ! 5 × 4 × 3 × 2 × 1 × 47 ! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = ( 26 × 2 ) × ( 17 × 3 ) × ( 10 × 5 ) × 49 × ( 12 × 4 ) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2,598,960. {\displaystyle {\begin{alignedat}{2}{52 \alege 5}&={\frac {52!}{5!47!}}\\&={\frac {52\timpuri 51\timpuri 50\timpuri 49\timpuri 48\timpuri {\anulare {47!}}}{5\timpuri 4\timpuri 3\timpuri 2\timpuri {\anulare {1}}\timpuri {\anulare {47!}}}}\\&={\frac {52\timpuri 51\timpuri 50\timpuri 49\timpuri 48}{5\timpuri 4\timpuri 3\timpuri 2}}\\\\&={\frac {(26\timpuri {\cancel {2}})\timpuri (17\timpuri {\cancel {3}})\timpuri (10\timpuri {\cancel {\cancel {5}}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\\&={26\times 17\times 10\times 49\times 12}\\&=2{,}598{,}960.\end{alignedat}}}
Un alt calcul alternativ, echivalent cu primul, se bazează pe scrierea
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 × ⋯ × ( n – ( k – 1 ) ) k , {\displaystyle {n \alege k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}}},}
ceea ce dă
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598,960 {\displaystyle {52 \alege 5}={\frac {52}{1}}\timpuri {\frac {51}{2}}\timpuri {\frac {50}{3}}\timpuri {\frac {49}{4}}\timpuri {\frac {48}{5}}=2{,}598{,}960}
.
Când este evaluată în următoarea ordine, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, aceasta poate fi calculată folosind doar aritmetica numerelor întregi. Motivul este că, atunci când are loc fiecare împărțire, rezultatul intermediar care se produce este el însuși un coeficient binomial, astfel încât nu apar niciodată resturi.
Utilizarea formulei simetrice în termeni de factoriali fără a efectua simplificări dă un calcul destul de extins:
( 52 5 ) = n ! k ! ( n – k ) ! = 52 ! 5 ! ( 52 – 5 ) ! = 52 ! 5 ! 47 ! = 80 , 658 , 175 , 170 , 943 , 878 , 571 , 660 , 636 , 856 , 403 , 766 , 975 , 289 , 505 , 440 , 883 , 277 , 824 , 000 , 000 , 000 , 000 120 × 258 , 623 , 241 , 511 , 168 , 180 , 642 , 964 , 355 , 153 , 611 , 979 , 969 , 197 , 632 , 389 , 120 , 000 , 000 , 000 = 2,598,960. {\displaystyle {\begin{aligned}{52 \choose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\&=2{,}598{,}960.\end{aligned}}}
Enumerarea k-combinărilorEdit
Se pot enumera toate k-combinările unui set dat S de n elemente într-o anumită ordine fixă, ceea ce stabilește o bijecție de la un interval de ( n k ) {\displaystyle {\tbinom {n}{k}}}}.
numere întregi cu ansamblul acestor k-combinări. Presupunând că S este el însuși ordonat, de exemplu S = { 1, 2, …, n }, există două posibilități naturale de ordonare a k-combinărilor sale: prin compararea mai întâi a celor mai mici elemente ale acestora (ca în ilustrațiile de mai sus) sau prin compararea mai întâi a celor mai mari elemente ale acestora. Cea din urmă opțiune are avantajul că adăugarea unui nou element cel mai mare la S nu va modifica partea inițială a enumerării, ci doar va adăuga noile k-combinări ale setului mai mare după cele anterioare. Repetând acest proces, enumerarea poate fi extinsă la nesfârșit cu k-combinări ale unor seturi din ce în ce mai mari. În plus, dacă se consideră că intervalele numerelor întregi încep de la 0, atunci combinația k de la un anumit loc i din enumerare poate fi calculată cu ușurință de la i, iar bijecția astfel obținută este cunoscută sub numele de sistem numeric combinatoriu. Ea este cunoscută și sub numele de „rank”/”ranking” și „unranking” în matematica computațională.
Există mai multe moduri de a enumera k combinații. O modalitate este de a vizita toate numerele binare mai mici decât 2n. Alegeți acele numere care au k biți nenule, deși acest lucru este foarte ineficient chiar și pentru n mic (de exemplu, n = 20 ar necesita vizitarea a aproximativ un milion de numere, în timp ce numărul maxim de combinații k permise este de aproximativ 186 mii pentru k = 10). Pozițiile acestor biți 1 într-un astfel de număr reprezintă o combinație k specifică din setul { 1, …, n }. O altă modalitate simplă și mai rapidă constă în urmărirea a k numere de index ale elementelor selectate, începând cu {0 … k-1} (bazat pe zero) sau {1 … k} (pe bază de unu) ca prima combinație k permisă și apoi trecând în mod repetat la următoarea combinație k permisă prin creșterea ultimului număr de index dacă acesta este mai mic decât n-1 (pe bază de zero sau n (pe bază de unu) sau a ultimului număr de index x care este mai mic decât numărul de index care îl urmează minus unu, dacă există un astfel de index, și resetarea numerelor de index după x la {x+1, x+2, …}.
.