Matematici aplicate în economie · Probabilități și statistică

Combinatorică

Intermediar60 min

Pe această pagină

Ce înveți

  • Alegi formula potrivită (permutări, aranjamente, combinări, cu sau fără repetiție) după două întrebări: contează ordinea și se pot repeta elementele.
  • Folosești proprietățile combinărilor, triunghiul lui Pascal și binomul lui Newton.
  • Numeri elementele unei reuniuni de mulțimi cu principiul includerii și excluderii.

Teorie

Probabilitățile clasice se calculează numărând: câte rezultate favorabile, din câte posibile. Combinatorica este arta de a număra fără să scrii toate variantele una câte una. În lecția „Elemente de logică și combinatorică” din primul curs ai întâlnit permutările, aranjamentele și combinările simple. Aici le aduni pe toate într-un singur tablou, adaugi cazurile cu repetiție și proprietățile care fac calculele rapide.

Partea 1. Regulile de bază

  • Regula sumei: dacă o alegere se face fie într-unul dintre m moduri, fie într-unul dintre n moduri, fără suprapuneri, există m+nm + n posibilități.
  • Regula produsului: dacă o alegere are k etape, cu n1,n2,…,nkn_1, n_2, \ldots, n_k variante la fiecare etapă, există n1⋅n2⋯nkn_1 \cdot n_2 \cdots n_k posibilități. Exemplu ipotetic: o cafenea oferă 4 tipuri de cafea, 3 tipuri de lapte și 2 mărimi, deci 4×3×2=244 \times 3 \times 2 = 24 de băuturi diferite.

Exemplu ipotetic: din 100 de clienți ai unei cafenele, 60 au cumpărat cafea, 45 un croissant, iar 25 ambele. Au cumpărat cel puțin unul dintre produse 60+45−25=8060 + 45 - 25 = 80 de clienți, iar 100−80=20100 - 80 = 20 nu au cumpărat niciunul dintre ele.

Partea 2. Două întrebări care aleg formula

Pentru orice problemă de numărare în care alegi k elemente dintr-o mulțime de n, pune-ți două întrebări: contează ordinea? și se pot repeta elementele? Răspunsurile aleg formula:

Fără repetițieCu repetiție
Ordinea conteazăaranjamente: Ank=n!(n−k)!A_n^k = \frac{n!}{(n-k)!}aranjamente cu repetiție: nkn^k
Ordinea nu conteazăcombinări: Cnk=n!k! (n−k)!C_n^k = \frac{n!}{k!\,(n-k)!}combinări cu repetiție: Cn+k−1kC_{n+k-1}^k

Cazul special k=nk = n, fără repetiție, este permutarea: Pn=n!P_n = n!, numărul de moduri de a așeza n elemente în ordine. Prin convenție, 0!=10! = 1.

Exemple ipotetice, câte unul pentru fiecare căsuță:

  • Aranjamente: un magazin alege, din 8 produse, câte unul pentru vitrina de sus, de mijloc și de jos. Ordinea contează (vitrinele sunt diferite), produsele nu se repetă: A83=8×7×6=336A_8^3 = 8 \times 7 \times 6 = 336 de variante.
  • Aranjamente cu repetiție: un cod de reducere are 4 cifre, care se pot repeta: 104=10 00010^4 = 10\,000 de coduri.
  • Combinări: un manager alege 3 angajați dintr-o echipă de 10 pentru un curs. Ordinea nu contează: C103=10×9×83×2×1=120C_{10}^3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120 de grupuri.
  • Combinări cu repetiție: o gogoșerie are 5 sortimente, iar o cutie conține 3 gogoși, care pot fi și de același fel. Ordinea din cutie nu contează: C5+3−13=C73=35C_{5+3-1}^3 = C_7^3 = 35 de cutii diferite.

Legătura dintre formule: Ank=Cnk⋅k!A_n^k = C_n^k \cdot k!, pentru că fiecare grup neordonat de k elemente se poate așeza în k!k! ordini. Echivalent, Cnk=AnkPkC_n^k = \frac{A_n^k}{P_k}.

Partea 3. Permutări cu repetiție

Când printre cele n elemente de așezat unele sunt identice, schimbarea lor între ele nu dă o ordine nouă. Dacă există n1n_1 elemente de primul fel, n2n_2 de al doilea și așa mai departe, cu n1+n2+…+nr=nn_1 + n_2 + \ldots + n_r = n, numărul de așezări diferite este:

Pn(n1,n2,…,nr)=n!n1! n2!⋯nr!P_n(n_1, n_2, \ldots, n_r) = \frac{n!}{n_1! \, n_2! \cdots n_r!}

Permutările cu repetiție numără, de exemplu:

  • anagramele unui cuvânt: CAFEA are 5 litere, dintre care A apare de două ori, deci 5!2!=60\frac{5!}{2!} = 60 de anagrame;
  • ordinile de livrare: un curier are 3 colete pentru firma A și 2 pentru firma B; dacă ține cont doar de firmă, există 5!3!⋅2!=10\frac{5!}{3! \cdot 2!} = 10 ordini diferite. Observă că rezultatul este egal cu C52C_5^2: alegi pozițiile celor 2 colete pentru B, restul sunt pentru A.

Partea 4. Proprietățile combinărilor și binomul lui Newton

Proprietăți pe care le folosești des:

  • Cn0=Cnn=1C_n^0 = C_n^n = 1 și Cn1=nC_n^1 = n;
  • combinări complementare: Cnk=Cnn−kC_n^k = C_n^{n-k} (a alege 3 angajați din 10 pentru curs înseamnă a alege 7 care rămân);
  • formula de recurență (a lui Pascal): Cnk=Cn−1k−1+Cn−1kC_n^k = C_{n-1}^{k-1} + C_{n-1}^k;
  • suma combinărilor: Cn0+Cn1+…+Cnn=2nC_n^0 + C_n^1 + \ldots + C_n^n = 2^n, adică numărul tuturor submulțimilor unei mulțimi cu n elemente. Un client care poate adăuga sau nu fiecare dintre 5 toppinguri are 25=322^5 = 32 de variante de pizza.

Așezate pe rânduri, combinările formează triunghiul lui Pascal: fiecare număr este suma celor două numere de deasupra lui.

nCombinările Cn0,Cn1,…,CnnC_n^0, C_n^1, \ldots, C_n^n
01
11, 1
21, 2, 1
31, 3, 3, 1
41, 4, 6, 4, 1
51, 5, 10, 10, 5, 1
61, 6, 15, 20, 15, 6, 1

Aplicație la dobânda compusă: o sumă depusă 3 ani cu 5% pe an crește de (1+0,05)3(1 + 0{,}05)^3 ori. Cu binomul, (1+0,05)3=1+3×0,05+3×0,052+0,053=1+0,15+0,0075+0,000125=1,157625(1 + 0{,}05)^3 = 1 + 3 \times 0{,}05 + 3 \times 0{,}05^2 + 0{,}05^3 = 1 + 0{,}15 + 0{,}0075 + 0{,}000125 = 1{,}157625. Primii doi termeni (1+0,151 + 0{,}15) sunt dobânda simplă; restul este „dobânda la dobândă”, mică la început, dar tot mai mare cu cât trec anii.

Video

How to Calculate Permutations and Combinations - Probability

de Jeremy Blitz-Jones

Se încarcă de pe YouTube

How to Calculate Permutations and Combinations - Probability · de Jeremy Blitz-Jones · Deschide pe YouTube

Întrebare-ghid: Clipul este în engleză (permutations = aranjamente sau permutări, combinations = combinări). Urmărește cum decide autorul dacă ordinea contează și compară cu tabelul din Partea 2.

Combinations with Repetition | Combinatorics

de Wrath of Math

Se încarcă de pe YouTube

Combinations with Repetition | Combinatorics · de Wrath of Math · Deschide pe YouTube

Întrebare-ghid: Clipul este în engleză și explică metoda „stelelor și barelor”. Urmărește de ce formula este C(n + k − 1, k) și aplic-o la cutiile de gogoși din Partea 2.

Exemple grafice

Primul grafic arată rândul n = 10 din triunghiul lui Pascal: în câte moduri poți alege k angajați dintr-o echipă de 10.

07515022530012345678910Câți angajați alegi (k)Număr de grupuriC(10, k)maxim: 252
Numărul de grupuri de k angajați dintr-o echipă de 10 crește până la k = 5 (252 de grupuri), apoi scade simetric, pentru că C(10, k) = C(10, 10 − k). Suma tuturor valorilor este 2¹⁰ = 1024.
Vezi datele ca tabel
Combinările de 10 luate câte k
SerieCâți angajați alegi (k)Număr de grupuri
C(10, k)01
C(10, k)110
C(10, k)245
C(10, k)3120
C(10, k)4210
C(10, k)5252
C(10, k)6210
C(10, k)7120
C(10, k)845
C(10, k)910
C(10, k)101
maxim: 2525252

Încearcă să verifici o valoare cu recurența lui Pascal: C104=C93+C94=84+126=210C_{10}^4 = C_9^3 + C_9^4 = 84 + 126 = 210. Concluzie: cele mai multe variante apar când alegi aproximativ jumătate din elemente; forma de „clopot” va reapărea la distribuția binomială.

Al doilea grafic compară, pentru coduri de k cifre, numărul de coduri cu cifre diferite (A10kA_{10}^k) cu numărul tuturor codurilor (10k10^k), ca procent.

025507510012345678Lungimea codului (k cifre)Coduri cu cifre diferite (%)A(10, k) : 10^kPIN de 4 cifre: 50,4%
Pentru 2 cifre, 90% din coduri au cifre diferite; pentru 4 cifre, 50,4%; pentru 6 cifre, doar 15,1%; pentru 8 cifre, 1,8%. Raportul este A(10, k) : 10^k.
Vezi datele ca tabel
Ce parte din coduri au toate cifrele diferite
SerieLungimea codului (k cifre)Coduri cu cifre diferite (%)
A(10, k) : 10^k1100
A(10, k) : 10^k290
A(10, k) : 10^k372
A(10, k) : 10^k450,4
A(10, k) : 10^k530,24
A(10, k) : 10^k615,12
A(10, k) : 10^k76,05
A(10, k) : 10^k81,81
PIN de 4 cifre: 50,4%450,4

Încearcă să calculezi pentru un PIN de 4 cifre: A104=10×9×8×7=5040A_{10}^4 = 10 \times 9 \times 8 \times 7 = 5040 de coduri cu cifre diferite din 10 00010\,000, adică 50,4%. Concluzie: repetițiile apar mult mai des decât ne-am aștepta, aceeași idee ca în „problema zilelor de naștere” din lecția următoare.

Aprofundare

De ce funcționează recurența lui Pascal

Fixezi unul dintre cele n elemente, de exemplu un angajat anume. Grupurile de k angajați sunt de două feluri: cele care îl conțin (alegi ceilalți k−1k - 1 dintre ceilalți n−1n - 1, adică Cn−1k−1C_{n-1}^{k-1} grupuri) și cele care nu îl conțin (alegi toți k dintre ceilalți n−1n - 1, adică Cn−1kC_{n-1}^k). Cele două feluri nu se suprapun, deci, după regula sumei, Cnk=Cn−1k−1+Cn−1kC_n^k = C_{n-1}^{k-1} + C_{n-1}^k.

Stele și bare

De ce sunt Cn+k−1kC_{n+k-1}^k combinări cu repetiție? O cutie cu 3 gogoși din 5 sortimente se poate scrie ca un șir de 3 stele (gogoșile) și 4 bare (care despart cele 5 sortimente). De exemplu, „★★||★||” înseamnă două gogoși din primul sortiment și una din al treilea. Orice cutie corespunde unui singur șir de 7 simboluri și invers, iar un șir este stabilit de locurile celor 3 stele printre cele 7 poziții: C73=35C_7^3 = 35.

Excepții și nuanțe

  • Așezări în cerc: n persoane în jurul unei mese rotunde se pot așeza în (n−1)!(n - 1)! moduri, nu n!n!, pentru că rotirea tuturor nu schimbă așezarea.
  • Atenție la „cel puțin”: numărul grupurilor cu cel puțin o femeie se calculează mai ușor prin complement: toate grupurile minus grupurile fără nicio femeie.
  • Formulele presupun că elementele sunt distincte (sau identice exact cum spune problema). Dacă două produse „diferite” sunt de fapt identice pentru client, numărarea se schimbă.

Un caz real: triunghiul lui Pascal, înainte de Pascal

Blaise Pascal a scris „Tratatul despre triunghiul aritmetic” în 1654 (publicat în 1665) și a folosit triunghiul pentru a rezolva probleme de jocuri de noroc. Același triunghi apare însă cu secole mai devreme: matematicianul chinez Yang Hui l-a publicat în 1261, iar în Persia el era cunoscut încă din secolul al XI-lea. De aceea, în China se numește „triunghiul lui Yang Hui”, iar în Iran „triunghiul lui Khayyam”.

Quiz

Verifică ce ai înțeles. Poți reîncerca oricând.

1. Un manager alege 3 angajați dintr-o echipă de 10 pentru un curs. Ce formulă folosești?

Alege o singură variantă.

2. Câte coduri de reducere de 4 cifre există, dacă cifrele se pot repeta?

Scrie un număr.

coduri

3. Câte anagrame are cuvântul CAFEA?

Scrie un număr.

4. O gogoșerie are 5 sortimente. Câte cutii diferite de 3 gogoși se pot face, dacă gogoșile pot fi și de același fel?

Scrie un număr.

cutii

5. Combinările de 10 luate câte 3 sunt egale cu combinările de 10 luate câte 7.

Alege o singură variantă.

6. Din 100 de clienți, 60 au cumpărat cafea, 45 un croissant și 25 ambele. Câți nu au cumpărat niciunul dintre cele două produse?

Scrie un număr.

clienți

7. Care este coeficientul lui x² în dezvoltarea lui (1 + x)⁶?

Scrie un număr.

8. Un client poate adăuga sau nu fiecare dintre 6 toppinguri la pizza. Câte variante are, inclusiv pizza fără niciun topping?

Scrie un număr.

variante