Combinare

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În matematică, o combinare reprezintă un mod de a selecta elementele unei mulțimi, așa încât (spre deosebire de permutări) ordinea selectării nu contează. În cazurile mai mici este posibil să numărăm toate combinările prin scrierea acestora. De exemplu, fiind date trei fructe (un măr, o portocală și o pară), există trei combinări a câte două fructe care pot fi extrase din acest set: un măr și o pară, un măr și o portocală, sau o pară și o portocală. Din punct de vedere formal, o k-combinare a unei mulțimi S este o submulțime de k elemente distincte ale lui S. Dacă această mulțime are n elemente, numărul k-combinărilor este egal cu coeficientul binomial.

 C_n^k = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1},

care poate fi scrisă utilizând factoriali drept  \frac{n!}{k!(n-k)!} atunci când  k \leqslant n și care este zero când  k \geqslant n. Mulțimea tuturor k-combinarilor a unei mulțimi S este, uneori, notată   \binom Sk\,.

Combinările se referă la combinarea de n lucruri luate câte k odată fără a se repeta. Pentru a face referire la combinările în care repetarea elementelor este permisă, sunt folosiți termeni precum k-selectie, k-multiset sau k-combinare cu repetiții. Dacă în exemplul de mai sus era posibil să avem două fructe de orice fel, ar mai fi existat încă trei 2-selectii: una cu două mere, una cu două portocale și una cu două pere.

Pentru mulțimi mari este necesar să utilizăm aspecte mai sofisticate ale matematicii pentru a găsi numărul combinărilor. De exemplu, o mână la poker poate fi descrisă ca o 5-combinare (k=5) de cărți dintr-un pachet de 52 (n=52) de cărți. Cele 5 cărți din mână sunt diferite și ordinea acestora în mână nu contează. Sunt 2.598.960 astfel de combinări posibile, iar șansa de a trage 5 cărți în mod aleator este de 1 / 2.598.960.

Numărul de k-combinări[modificare | modificare sursă]

Combinări fără repetiţii de 5 luate câte 3

Numărul k-combinarilor dintr-o mulțime dată S cu n elemente este, de obicei, notat, în combinatorica elementară  C(n, k) sau oricare dintre aceste moduri: {}_nC_k, {}^nC_k, sau C_n^k (ultima formă constituie standardul folosit în România, Franța, Rusia, China). Același număr, totuși, apare în multe alte contexte matematice, unde este notat drept C_n^k; în mod notabil, apare drept coeficient în formula binomială, de acolo provenindu-i și numele de coeficient binomial. Putem defini C_n^k pentru toate numerele natural k într-o singură expresie prin relația

\textstyle(1+X)^n=\sum_{k\geq0}C_n^k X^k,

din care se observă clar că C_n^0=C_n^n=1 și C_n^k=0 pentru k > n. Pentru a vedea că acești coeficienți numără k-combinatii din S, putem considera o colecție de n variabile distincte Xs identificate de elementele s ale mulțimii S și extinde produsul așa încât să cuprindă toate valorile din S:

\textstyle\prod_{s\in S}(1+X_s);

aceasta are 2^n termeni diferiți ce corespund tuturor submulțimilor lui S, fiecare submulțime oferind produsul variabilelor corespunzătoare Xs.

Coeficienții binomiali pot fi calculați explicit în numeroase moduri. Pentru a îi afla pe toți pentru explicitări până la (1 + X)^n, putem folosi (pe lângă cazurile de bază abordate deja) relația de recurență

C_n^k=C_{n-1}^{k-1}+C_{n-1}^k,\text{ for }0<k<n,

care se poate scrie sub forma (1 + X)^n = (1 + X)^{n-1}(1 + X); acest fapt duce la construirea triunghiului lui Pascal.

Pentru a determina un coeficient binomial individual, este mai practic să folosim formula

 C_n^k = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.

Numărătorul constituie numărul de k-permutări de n elemente (secvențe de k valori distincte din mulțimea S), în timp ce numitorul reprezintă numărul de astfel de k-permutări care dau aceeași k-combinație când ordinea este ignorată.

Atunci când k depășește n/2, formula de mai sus conține factori comuni între numărător și numitor și, prin simplificarea acestora, obținem relația

C_n^k = C_n^{n-k},\text{ for }0 \le k \le n.

Aceasta exprimă o simetrie evidentă din formula binomială și poate fi, de asemenea, înțeleasă drept k-combinări, prin eliminarea complementului unei astfel de combinări, ce constituie o (n-k)-combinare.

În final, există o formulă care se folosește în mod frecvent și redă simetria direct, având calitatea de a fi ușor de memorat:

C_n^k = \frac{n!}{k!(n-k)!},

unde n! reprezintă factorialul lui n.

Ultima formulă poate fi înțeleasă direct, prin considerarea celor n! permutări ale tuturor elementelor mulțimii S. Din fiecare dintre aceste permutări se poate obține o k-combinatie, prin selectarea primelor k elemente. Există multe selecții duplicate: oricare permutare combinată a primelor k elemente între ele și a ultimelor (n-k) elemente între ele produce aceeași combinație; acest lucru explică împărțirea din formulă.

Din formulele de mai sus rezultă relații între numere adiacente în triunghiul lui Pascal în toate cele trei direcții:

C_n^k = C_n^{k-1} \frac {n-k+1}k,\text{ for }k>0 ,

C_n^k = C_{n-1}^k \frac n{n-k},\text{ for }{k<n} ,

C_n^k = C_{n-1}^{k-1} \frac nk,\text{ for }n,k>0 .

Împreună cu cazurile de bază C_n^0 = 1 = C_n^n, acestea permit calcularea succesivă a tuturor numerelor de combinări din același set (o linie din triunghiul lui Pascal), a k-combinărilor de mulțimi cu mărimi crescătoare și a combinărilor cu un complement de mărime fixă (n-k).

Exemple de numărare a combinărilor[modificare | modificare sursă]

De exemplu, putem calcula numărul combinărilor posibilie pentru alcătuirea unei mâini de 5 cărți dintr-un pachet standard de 52:

C_{52}^5 = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311{,}875{,}200}{120} = 
2{,}598{,}960.

Totodată, putem folosi formula combinărilor utilizând factorialii și simplifica factorii de la numărător cu o parte din factorii de la numitor, după care va rămâne de efectuat doar înmulțirea factorilor rămași:


\begin{alignat}{2}C_{52}^5 &= \frac{52!}{5!47!} \\
&= \frac{52\times51\times50\times49\times48\times\cancel{47!}}{5\times4\times3\times2\times\cancel{1}\times\cancel{47!}} \\
&= \frac{52\times51\times50\times49\times48}{5\times4\times3\times2} \\
&= \frac{(26\times\cancel{2})\times(17\times\cancel{3})\times(10\times\cancel{5})\times49\times(12\times\cancel{4})}{\cancel{5}\times\cancel{4}\times\cancel{3}\times\cancel{2}} \\
&= {26\times17\times10\times49\times12} \\&= 2{,}598{,}960.\end{alignat}

Un alt calcul alternativ, echivalent cu primul, este bazat pe scrierea


C_n^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 duce la


C_n^k = \frac{52}1 \times \frac{51}2 \times \frac{50}3 \times \frac{49}4 \times \frac{48}5 = 2{,}598{,}960.

Când evaluăm în următoarea ordine, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, această expresie poate fi calculată doar folosind operații cu numere întregi. Motivul este acela că atunci când are loc împărțirea, rezultatul intermediar care este produs este el însuși un coeficient binomial, deci nu va rămâne niciodată vreun rest.


\begin{align}
C_n^k &= \frac{n!}{k!(n-k)!} = \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\times258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000} \\
&= 2{,}598{,}960.
\end{align}

Enumerarea a k-combinări[modificare | modificare sursă]

Putem enumera toate cele k-combinări ale unei mulțimi S cu n elemente într-o ordine fixă, care va stabili o relație de bijectivitate între un interval de C_n^k numere întregi și setul respectivelor k-combinari. Asumând faptul că S este ordonată (de exemplu S={1,2,...,n}), există două posibilități naturale de a ordona cele k-combinari posibile pentru această mulțime: comparând cele mai mici elemente ale lor pentru început (ca în imaginea de mai sus) sau comparând cele mai mari elemente inițial. A doua opțiune are avantajul că a adauga un nou element cu valoare maximă la S nu va schimba partea inițială a enumerării, ci va pune cele k-combinari noi din mulțimea mai mare după cele precedente. Repetând acest proces, enumerația se poate extinde indefinit cu k-combinari de mulțimi din ce în ce mai mari. Dacă intervalele de numere întregi pornesc de la 0, atunci k-combinarea de pe un loc dat i din enumerație va putea fi calculată ușor din i, iar bijecția astfel obținută va fi cunoscută sub numele de sistem combinatorial de numarare.

Numărul k-combinărilor pentru toate numerele k[modificare | modificare sursă]

Numărul k-combinărilor pentu toate valorile valide ale lui k reprezintă numărul de submulțimi ale unei mulțimi cu n elemente. Există câteva moduri de a demonstra că acest număr este 2^n. În termeni combinatorici, \sum_{0\leq{k}\leq{n}}C_n^k = 2^n, reprezentând suma celei de-a n-a linii (începând numărătoarea de la 0) a coeficienților binomiali din triunghiul lui Pascal. Aceste combinări (submulțimi) sunt enumerate prin cifrele 1 din mulțimea de numere în baza 2, începând de la 0 până la 2^n-1, unde fiecare poziție a cifrei este un element din mulțimea S de n elemente.

Fiind date 3 cărți numerotate de la 1 la 3, există 8 combinații distincte (submulțimi) ce se pot forma, inclusiv mulțimea vidă:

| \{ \{\}  ;  \{1\}  ;  \{2\}  ;  \{3\}  ;  \{1, 2\}  ;  \{1, 3\}  ;  \{2, 3\}  ;  \{1, 2, 3\} \}| = 2^3 = 8

Vezi și[modificare | modificare sursă]

Note[modificare | modificare sursă]

  1. Ryser 1963, p. 7
  2. Mazur 2010, p. 10
  3. High School Textbook for full-time student (Required) Mathematics Book II B (in Chinese) (2nd ed.). China: People's Education Press. June 2006. pp. 107–116. ISBN 978-7-107-19616-4.
  4. Mazur 2010, p. 21
  5. http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf
  6. http://www.sagemath.org/doc/reference/sage/combinat/subset.html
  7. http://rosettacode.org/wiki/Combinations
  8. Brualdi 2010, p. 52
  9. Benjamin & Quinn 2003, p. 70
  10. Benjamin & Quinn 2003, pp. 71 –72
  11. Benjamin & Quinn 2003, p. 72
  12. Benjamin & Quinn 2003, p. 71
  13. Mazur 2010, p. 10

Referințe[modificare | modificare sursă]

  • Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7
  • Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pearson Prentice Hall, ISBN 978-0-13-602040-0
  • Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
  • Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Association of America, ISBN 978-0-88385-762-5
  • Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs 14, Mathematical Association of America