Faceți căutări pe acest blog

miercuri, 10 septembrie 2014

Alte proprietăți ale combinărilor


Așa cum vă povesteam într-un articol precedent, combinările (deci, coeficienții binomiali ce apar în dezvoltarea binomului lui Newton) se regăsesc în triunghiul lui Pascal:

$$\begin{matrix}
n=0&&&&&&&&1&&&&&&&&&&\\
n=1&&&&&&&1&&1&&&&&&&&&\\
n=2&&&&&&1&&1+1&&1&&&&&&&&\\
n=3&&&&&1&&1+2&&2+1&&1&&&&&&&\\
n=4&&&&1&&1+3&&3+3&&3+1&&1&&&&\\
n=5&&&1&&1+4&&4+6&&6+4&&4+1&&1&&\\
\end{matrix}.$$

Acest triunghi este, desigur, nelimitat în jos, dar noi ne folosim doar de câteva linii relevante din care putem extrage alte proprietăți interesante ale combinărilor.

Cea mai clară proprietate este recurența combinărilor, ce exprimă tocmai modul în care este construit acest triunghi. Mai exact, vă amintiți că fiecare coeficient poate fi scris ca o sumă formată cu cei doi coeficienți vecini aflați pe rândul precedent.

De exemplu, pentru rândul corespunzător puterii 4 avem că
$$4=C_4^1=\color{blue}{C_{3+1}^{0+1}=C_3^0+C_3^1}=1+3,$$
$$6=C_4^2=\color{blue}{C_{3+1}^{1+1}=C_3^1+C_3^2}=3+3,$$
$$4=C_4^3=\color{blue}{C_{3+1}^{2+1}=C_3^2+C_3^3}=3+1,$$
iar pentru rândul corespunzător puterii 5 avem
$$5=C_5^1=\color{blue}{C_{4+1}^{0+1}=C_4^0+C_4^1}=1+4,$$
$$10=C_5^2=\color{blue}{C_{4+1}^{1+1}=C_4^1+C_4^2}=4+6,$$
$$10=C_5^3=\color{blue}{C_{4+1}^{2+1}=C_4^2+C_4^3}=6+4,$$
$$5=C_5^4=\color{blue}{C_{4+1}^{3+1}=C_4^3+C_4^4}=4+1.$$

Desigur, această recurență se păstrează mereu pentru orice rând al triunghiului. Asta înseamnă că putem înlocui numerele concrete care apar mai sus cu litere. Printr-o asemenea înlocuire rezultă o formulă de recurență de toată frumusețea:
$$\large{\color{red}{C_{n+1}^{k+1}=C_n^k+C_n^{k+1}}},$$
unde trebuie doar să avem grijă la ce numere punem în locul literelor ca să nu iasă cumva în partea de jos a combinărilor un număr mai mic decât în partea de sus.

Alte proprietăți ale combinărilor rezultă tocmai din modul lor de calcul. Avem două modalități de calcul al combinărilor: o modalitate care folosește aranjamentele și alta care folosește numai factorialul. 

Modalitatea cu aranjamentele se pate observa în exemplul următor
$$C_{10}^3=\frac{A_{10}^3}{3!}=\frac{10\cdot 9\cdot 8}{1\cdot 2\cdot 3}.$$
Observați că în acest exemplu numărătorul pornește de la 10 și are 3 factori. Dacă am avea de calculat $C_{11}^2$ numărătorul ar porni de la 11 și ar avea 2 factori, deci am avea
$$C_{11}^2=\frac{A_{11}^2}{2!}=\frac{11\cdot 10}{1\cdot 2}.$$

Modalitatea cu factorialul rezultă din exemplul
$$C_{10}^3=\frac{10!}{3!\cdot(10-3)!}=\frac{10!}{3!\cdot 7!},$$
respectiv, din exemplul
$$C_{11}^2=\frac{11!}{2!\cdot(11-2)!}=\frac{11!}{2!\cdot 9!}.$$

Modalitatea cu aranjamentele vă scutește de scrierea explicită a factorialului mare de la numărător și vă sugerează de multe ori forma acestui numărător atunci când vi se cere să rezolvați o ecuație cu combinări care conțin litere în partea de jos.




În fine, mai povestim despre o ultimă formulă, foarte utilă în anumite probleme în care apar sume urâte cu combinări consecutive. Pornim de la un exemplu concret pentru a ne da seama ce se întâmplă, după care vom înlocui numerele cu litere. 

Calculăm prin modalitatea cu factorialul $C_9^4$ și obținem
$$C_9^4=\frac{9!}{4!\cdot 5!}.$$
Acum vrem să vedem dacă putem găsi vreo legătură între $C_9^4$ și $C_8^3$. Pentru aceasta, calculăm și $C_8^3$ și obținem
$$C_8^3=\frac{8!}{3!\cdot 5!}.$$
Să vedem acum care o fi legătura dintre $C_9^4$ și $C_8^3$. Observăm că $9!=9\cdot 8!$ și că $4!=4\cdot 3!$. Înlocuind, obținem
$$C_9^4=\frac{9!}{4!\cdot 5!}=\frac{9\cdot 8!}{4\cdot 3!\cdot 5!}=\frac{9}{4}\cdot\frac{8!}{3!\cdot 5!}=\frac{9}{4}C_8^3.$$
Sper că ați observat acum legătura dintre cele două combinări. Apare o fracție între cele două combinări, al cărei numărător și numitor conține tocmai numerele ce apar la combinarea cu numerele mai mari.
Așadar, am mai avea de exemplu 
$$C_{213}^{25}=\frac{213}{25}C_{212}^{24}.$$

Suntem, deci, în posesia unei alte formule de recurență cu ajutorul căreia obținem o combinare cu numere mari dintr-o combinare cu numere mai mici:
$$\large{\color{red}{C_{\color{blue}{n}}^{\color{green}{k}}=\frac{\color{blue}{n}}{\color{green}{k}}C_{n-1}^{k-1}}}.$$

Desigur, dacă vă place mai mult, fracția se poate aduce lângă prima combinare, doar că atunci trebuie răsturnată și avem ceva parcă mai simetric:
$$\large{\color{red}{\frac{\color{green}{k}}{\color{blue}{n}}C_{\color{blue}{n}}^{\color{green}{k}}=C_{n-1}^{k-1}}}.$$

Gata, v-am împuiat capul destul cu formule pentru combinări. Sunt chiar prea multe pentru bac și poate nu veți avea nevoie niciodată de toate. Bineînțeles, eu aș prefera totuși să le învățați în eventualitatea că veți avea nevoie de ele mai departe în viață.