Aranjamente

Folosim aranjamentele atunci când alegem dintr-o mulțime de obiecte un anumit număr de obiecte și contează ordinea în care le alegem.

Deducerea formulei

Începem cu o problemă tipică de aranjamente: într-un sat se organizează în fiecare an un concurs de mâncat găluște cu prune. În finală au ajuns în total șapte concurenți mânjiți din cap până în picioare. Află în câte moduri pot ocupa acești șapte participanți primele trei locuri.

Este important să înțelegem că în acest exemplu contează ordinea. De pildă, dacă știm că pe primele trei locuri se clasează Andrei, Mihai și Vlad, atunci acest trio ne dă în total șase clasamente diferite:

Andrei, Mihai, Vlad;
Andrei, Vlad, Mihai;
Mihai, Andrei, Vlad;
Mihai, Vlad, Andrei;
Vlad, Andrei, Mihai;
Vlad, Mihai, Andrei.

Toate acestea sunt clasamente diferite, iar noi vrem să aflăm câte clasamente diferite putem alcătui în total când concurenții sunt 7.

Folosim pentru asta regula produsului. Spunem că alegem triplete de forma (x₁, x₂, x₃), unde x₁ este concurentul care a terminat pe primul loc și așa mai departe. Pe cine putem pune în locul lui x₁? Pe oricare, deci în locul lui x₁ putem pune 7 concurenți. Pe cine putem pune în locul lui x₂? Pe oricare, în afară de cel pe care l-am pus deja pe primul loc, deci în locul lui x₂ putem pune 7 − 1 = 6 concurenți. În locul lui x₃ putem pune apoi concurenții care nu sunt pe primul sau pe al doilea loc, deci avem 7 − 2 = 5 posibilități. Aplicăm regula produsului și obținem numărul total de posibilități: 7 · 6 · 5 = 210.

Observăm că, dacă vrem numărul tuturor posibilităților pentru primele 4 locuri, în locul lui x₄ putem pune 7 − 3 = 4 concurenți, deci numărul total de posibilități va fi 7 · 6 · 5 · 4 = 840. Ce putem deduce de aici?

Dacă avem o mulțime cu n elemente (aici, în exemplu, 7 concurenți) și alegem 3 elemente, contând ordinea, atunci rezultatul este egal cu n · (n − 1) · (n − 2). Pe primul loc se pot clasa toți, pe următorul cu unul mai puțin și așa mai departe. De aici putem deduce formula generală pentru alegerea a k elemente dintr-o mulțime cu n elemente: numărul de posibilități va fi egal cu n · (n − 1) · (n − 2) · … · (n − k + 1).

Mai transformăm această formulă cu ajutorul factorialului. Dacă ne uităm la factorialul lui șapte, 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1, și la cum am calculat numărul tuturor clasamentelor pe podium, 7 · 6 · 5, vedem o anumită asemănare. Trebuie doar să scăpăm de coada produsului, adică trebuie să împărțim 7! la 4 · 3 · 2 · 1, iar astfel ne rămâne doar 7 · 6 · 5. Și cu ce este egală expresia 4 · 3 · 2 · 1? Este egală cu 4!.

Putem deci scrie că, dacă avem o mulțime cu n elemente și alegem în total k elemente, contând ordinea, avem în total

$A_{n}^{k} = \frac{n!}{(n - k)!}$

posibilități. Dacă înlocuim în formulă numerele din concursul de găluște:

$A_{7}^{3} = \frac{7!}{(7 - 3)!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = 7 \cdot 6 \cdot 5 = 210.$

Calculator

Calculatorul de mai jos calculează numărul aranjamentelor pentru n și k date.

Exemple rezolvate

Rămânem la concursul de mâncat găluște. Cum s-ar schimba numărul clasamentelor posibile pe podium dacă am ști că la concurs a venit Victor Schmidt, un maestru care câștigă întotdeauna? Adică: câte clasamente diferite pe podium există, dacă avem 7 concurenți și Victor câștigă sigur?

Este din nou un aranjament simplu: primul loc este sigur, iar dintre ceilalți 6 concurenți trebuie să stabilim cum pot ocupa locul al doilea și locul al treilea. Alegem deci 2 elemente dintr-o mulțime cu 6 elemente, ceea ce duce la aranjamentul

$A_{6}^{2} = \frac{6!}{(6 - 2)!} = 30$

Cândva, când Victor Schmidt nu era încă un maestru, se clasa de obicei printre primii trei. Câte clasamente diferite pe podium există, dacă avem 7 concurenți și Victor primește sigur o medalie?

Acest exemplu diferă de cel anterior prin faptul că nu știm pe ce loc s-a clasat Victor; ar fi putut să fie al doilea sau chiar al treilea, lucru de care încă îi este rușine. De aceea trebuie să calculăm în total trei aranjamente diferite: cazul în care Victor a câștigat, apoi cazul în care Victor ar fi obținut medalia de argint și, în sfârșit, cea de bronz. De fiecare dată rămân însă doar două locuri pe care se poate clasa altcineva. Dacă, de exemplu, Victor a fost al doilea, ceilalți participanți s-ar fi putut clasa fie pe primul, fie pe al treilea loc. Calculăm deci din nou aranjamente de câte două elemente din șase, doar că trebuie să le calculăm de trei ori, pentru cele trei clasări diferite ale lui Victor. Numărul tuturor clasamentelor este deci egal cu:

$3 \cdot A_{6}^{2} = 3 \cdot \frac{6!}{(6 - 2)!} = 3 \cdot 30 = 90$

Observă că acel 3 din fața aranjamentului îl putem scrie ca $A_{3}^{1}$ , deoarece, de fapt, alegem un element (un anumit loc) dintr-o mulțime cu trei elemente (cele trei poziții de pe podium).
La o școală sunt în total 20 de profesori. În curând vor fi examenele de bacalaureat și trebuie alcătuită o comisie cu următoarea componență: un președinte, un membru blând și un membru sever. Câte posibilități există în total?

Mai întâi trebuie să răspundem la întrebarea dacă ordinea contează – da, contează, pe cei trei profesori îi putem aranja din nou în șase moduri diferite. Acum e simplu – alegem un aranjament de 3 elemente din 20:

$A_{20}^{3} = \frac{20!}{17!} = 6840.$
Câte numere de trei cifre putem forma din cifrele {0, 1, 2, 3, 4, 5}, dacă nicio cifră nu se poate repeta?

Contează ordinea? Da, contează, 123 este alt număr decât 321. Câte triplete diferite există? Este un simplu aranjament de 3 elemente din 6:

$A_{6}^{3} = \frac{6!}{3!} = 120.$

Dar mai trebuie să scădem aranjamentele care au zero pe primul loc, pentru că 012 nu este un număr de trei cifre. Întrebarea este acum: câte triplete diferite încep cu zero? În acest caz se schimbă cifrele doar pe celelalte două locuri (tripletele au forma (0, x₂, x₃)), așa că ne întrebăm câte perechi diferite putem forma folosind numerele {1, 2, 3, 4, 5}. Este din nou simplu: $A_{5}^{2} = 5! / 3! = 20$ . Există deci 20 de triplete care încep cu zero.

Numărul total de numere de trei cifre formate din cifrele {0, 1, 2, 3, 4, 5} este deci 120 − 20 = 100.
Câte numere diferite de trei cifre putem forma din cifrele {1, 2, 3, 4, 5}, dacă nicio cifră nu se poate repeta, iar numărul obținut trebuie să fie impar?

Ordinea contează, pentru că 123 este alt număr decât 321. Formăm un număr de trei cifre care este impar, ceea ce înseamnă că pe primele două poziții poate fi orice cifră, dar pe ultima trebuie să fie una dintre cifrele {1, 3, 5}. Mai întâi calculăm numărul tuturor tripletelor pe care le putem forma cu cele cinci cifre: $A_{5}^{3} = 5! / 2! = 60$ .

Fiecare cifră va apărea pe ultimul loc la fel de des, deci, dacă avem 5 cifre, fiecare cifră va apărea pe ultimul loc de 60 / 5 = 12 ori. Avem trei cifre {1, 3, 5} care pot apărea pe ultimul loc, deci avem 12 numere diferite care se termină cu 1, 12 numere care se termină cu 3 și 12 numere care se termină cu 5. Folosim regula sumei și obținem în total 12 + 12 + 12 = 36 posibilități.
Rezolvă ecuația $A_{x}^{2} = 72$ . Altfel spus: dintr-o mulțime cu x elemente alegem perechi ordonate și știm că putem alege în total 72 de perechi diferite. Câte elemente avea mulțimea din care am ales perechile? Scriem ecuația dezvoltat:

$A_{x}^{2} = \frac{x!}{(x - 2)!} = 72$

Transformăm mai departe:

$\begin{array}{rcl} \frac{x!}{(x - 2)!} & = & 72 \\ \frac{x \cdot (x - 1) \cdot (x - 2)!}{(x - 2)!} & = & 72 \\ x \cdot (x - 1) & = & 72 \\ x^{2} - x & = & 72 \\ x^{2} - x - 72 & = & 0 \end{array}$

Aceasta este deja o ecuație de gradul al doilea clasică, pe care o rezolvăm cu ajutorul discriminantului sau putem rescrie ecuația sub forma

$(x + 8) \cdot (x - 9) = 0$

din care putem citi soluțiile: x₁ = −8 și x₂ = 9. Soluția negativă nu ne interesează, pentru că o mulțime nu poate avea cardinal negativ, deci soluția ecuației inițiale este x = 9, mulțimea avea nouă elemente.

Surse și lecturi suplimentare

Bělohlávek, Vychodil: Diskrétní matematika (în limba cehă)

Capitole: Combinatorică, Aranjamente, Permutări, Combinări, Aranjamente cu repetiție, Combinări cu repetiție, Câte coduri PIN există?

« Anterior: Combinatorică

Următor: Permutări »