Matematici aplicate în economie · Probabilități și statistică
Combinatorică
Intermediar60 min✓ Terminată
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ă posibilități.
- Regula produsului: dacă o alegere are k etape, cu variante la fiecare etapă, există posibilități. Exemplu ipotetic: o cafenea oferă 4 tipuri de cafea, 3 tipuri de lapte și 2 mărimi, deci 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 de clienți, iar 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ție | Cu repetiție | |
|---|---|---|
| Ordinea contează | aranjamente: | aranjamente cu repetiție: |
| Ordinea nu contează | combinări: | combinări cu repetiție: |
Cazul special , fără repetiție, este permutarea: , numărul de moduri de a așeza n elemente în ordine. Prin convenție, .
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ă: de variante.
- Aranjamente cu repetiție: un cod de reducere are 4 cifre, care se pot repeta: de coduri.
- Combinări: un manager alege 3 angajați dintr-o echipă de 10 pentru un curs. Ordinea nu contează: 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ă: de cutii diferite.
Legătura dintre formule: , pentru că fiecare grup neordonat de k elemente se poate așeza în ordini. Echivalent, .
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ă elemente de primul fel, de al doilea și așa mai departe, cu , numărul de așezări diferite este:
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 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ă ordini diferite. Observă că rezultatul este egal cu : 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:
- și ;
- combinări complementare: (a alege 3 angajați din 10 pentru curs înseamnă a alege 7 care rămân);
- formula de recurență (a lui Pascal): ;
- suma combinărilor: , 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 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.
| n | Combinările |
|---|---|
| 0 | 1 |
| 1 | 1, 1 |
| 2 | 1, 2, 1 |
| 3 | 1, 3, 3, 1 |
| 4 | 1, 4, 6, 4, 1 |
| 5 | 1, 5, 10, 10, 5, 1 |
| 6 | 1, 6, 15, 20, 15, 6, 1 |
Aplicație la dobânda compusă: o sumă depusă 3 ani cu 5% pe an crește de ori. Cu binomul, . Primii doi termeni () 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.
Vezi datele ca tabel
| Serie | Câți angajați alegi (k) | Număr de grupuri |
|---|---|---|
| C(10, k) | 0 | 1 |
| C(10, k) | 1 | 10 |
| C(10, k) | 2 | 45 |
| C(10, k) | 3 | 120 |
| C(10, k) | 4 | 210 |
| C(10, k) | 5 | 252 |
| C(10, k) | 6 | 210 |
| C(10, k) | 7 | 120 |
| C(10, k) | 8 | 45 |
| C(10, k) | 9 | 10 |
| C(10, k) | 10 | 1 |
| maxim: 252 | 5 | 252 |
Încearcă să verifici o valoare cu recurența lui Pascal: . 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 () cu numărul tuturor codurilor (), ca procent.
Vezi datele ca tabel
| Serie | Lungimea codului (k cifre) | Coduri cu cifre diferite (%) |
|---|---|---|
| A(10, k) : 10^k | 1 | 100 |
| A(10, k) : 10^k | 2 | 90 |
| A(10, k) : 10^k | 3 | 72 |
| A(10, k) : 10^k | 4 | 50,4 |
| A(10, k) : 10^k | 5 | 30,24 |
| A(10, k) : 10^k | 6 | 15,12 |
| A(10, k) : 10^k | 7 | 6,05 |
| A(10, k) : 10^k | 8 | 1,81 |
| PIN de 4 cifre: 50,4% | 4 | 50,4 |
Încearcă să calculezi pentru un PIN de 4 cifre: de coduri cu cifre diferite din , 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 dintre ceilalți , adică grupuri) și cele care nu îl conțin (alegi toți k dintre ceilalți , adică ). Cele două feluri nu se suprapun, deci, după regula sumei, .
Stele și bare
De ce sunt 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: .
Excepții și nuanțe
- Așezări în cerc: n persoane în jurul unei mese rotunde se pot așeza în moduri, nu , 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.