Probleme de numărare

Problemele de numărare presupun determinarea numărului de mulţimi finite, în care poate conta sau nu ordinea elementelor.

Numărul grupelor de câte \displaystyle k elemente care se pot obţine utilizând cele \displaystyle n elemente ale unei mulţimi finite (\displaystyle k\leq n ).

  • În cazul în care cele \displaystyle k elemente ale unei grupe sunt distincte şi contează ordinea în care sunt aşezate în cadrul unei grupe, atunci numărul de grupe care se poate forma este \displaystyle A_{n}^{k} .
  • În cazul în care cele \displaystyle k elemente ale unei grupe sunt distincte, fără a conta ordinea în care sunt aşezate, atunci numărul de grupe care se poate forma este \displaystyle C_{n}^{k} .
  • În cazul în care cele \displaystyle k elemente ale unei grupe nu sunt neapărat distincte, numărul grupelor care se poate forma este \displaystyle n^{k} .

 

Reguli generale ale combinatoricii

Regula sumei: Dacă un anumit obiect \displaystyle A poate fi ales în \displaystyle m moduri, iar un alt obiect \displaystyle B poate fi ales în \displaystyle n moduri, atunci alegerea lui \displaystyle A sau \displaystyle B poate fi realizată în \displaystyle \left ( m+n \right ) moduri.

Regula produsului: Dacă un anumit obiect \displaystyle A poate fi ales în \displaystyle m moduri şi dacă, după fiecare alegere a lui \displaystyle A , un alt obiect \displaystyle B poate fi ales în \displaystyle n moduri, atunci numărul de perechi \displaystyle \left ( A, B \right ) care poate fi obţinut este egal cu \displaystyle \left ( m\cdot n \right ).

Extinzând ideea, dacă pentru fiecare alegere a unui obiect \displaystyle A dintre cele \displaystyle m obiecte date, există posibilitatea de a alege obiectul \displaystyle B în \displaystyle n moduri, şi pentru fiecare alegere a lui \displaystyle B există posibilitatea de a alege un al treilea obiect \displaystyle C în \displaystyle q moduri, atunci numărul total de triplete \displaystyle \left ( A,B,C \right ) care se pot obţine este egal cu \displaystyle \left ( m\cdot n\cdot q\right ) .

Numărul de funcţii

Presupunem mulţimile finite \displaystyle A=\left \{ x_{1},x_{2}, \ldots,x_{k} \right \} cu \displaystyle card\left ( A \right )=k şi \displaystyle B=\left \{ y_{1},y_{2}, \ldots,y_{n} \right \} cu \displaystyle card\left ( B \right )=n , \displaystyle k\leq n , şi mulţimea funcţiilor \displaystyle f:A\rightarrow B . Funcţia \displaystyle f asociază setului de valori distincte \displaystyle x_{1},x_{2}, \ldots,x_{k} , setul de valori \displaystyle y_{1},y_{2}, \ldots,y_{k} , distincte sau nu.

Numărul total de funcţii

\displaystyle f\left ( x_{1} \right ) poate lua oricare dintre cele \displaystyle n valori \displaystyle y_{1},y_{2}, \ldots,y_{n} posibile. Pentru fiecare dintre valorile luate de \displaystyle f\left ( x_{1} \right ) , \displaystyle f\left ( x_{2} \right ) poate lua, de asemenea, oricare dintre cele \displaystyle n valori \displaystyle y_{1},y_{2}, \ldots,y_{n} posibile, ş.a.m.d.

Aplicând regula produsului, numărul total de funcţii \displaystyle f:A\rightarrow B este egal cu

\displaystyle \underset{\textrm{de}\: k\: \textrm{ori}}{\underbrace{n\cdot n\cdot n \cdot \ldots \cdot n}}=n^{k}

Numărul de funcţii injective

Funcţia \displaystyle f este injectivă dacă pentru orice \displaystyle x_{i}\neq x_{j} , \displaystyle f\left (x_{i} \right )\neq f\left (x_{j} \right ) .

Prin urmare, valorile \displaystyle y_{1},y_{2}, \, \ldots \,, y_{k} pe care le poate lua funcţia \displaystyle f trebuie să fie distincte, deci \displaystyle \left \{ y_{1},y_{2}, \, \ldots \,, y_{k} \right \} este o submulţime cu \displaystyle k elemente a mulţimii \displaystyle B . Dacă ordinea valorilor se modifică, se obţine o funcţie diferită.

Astfel, numărul total de funcţii injective este egal cu numărul submulţimilor ordonate cu \displaystyle k elemente ale mulţimii \displaystyle B , respectiv \displaystyle A_{n}^{k} .

Numărul de funcţii bijective

Funcţia \displaystyle f este bijectivă dacă pentru orice \displaystyle x_{i}\neq x_{j} , \displaystyle f\left (x_{i} \right )\neq f\left (x_{j} \right ) şi pentru orice \displaystyle y_{i}\in B , există \displaystyle x_{i}\in A , astfel încât \displaystyle f\left (x_{i} \right )=y_{i} .

Prin urmare, funcţia \displaystyle f este bijectivă atunci când valorile \displaystyle y_{1},y_{2}, \, \ldots \,, y_{k} sunt distincte şi \displaystyle card\left ( A \right )=card\left ( B \right )=n (respectiv \displaystyle k=n ).

Prin urmare, numărul total de funcţii bijective este egal numărul de submulţimi ordonate cu \displaystyle n elemente ale mulţimii \displaystyle B , adică \displaystyle P_{n} .

Numărul de funcţii strict monotone

Funcţia \displaystyle f este strict crescătoare dacă pentru orice \displaystyle x_{i}<x_{j} , \displaystyle f\left (x_{i} \right )<f\left (x_{j} \right ) .

Funcţia \displaystyle f este strict descrescătoare dacă pentru orice \displaystyle x_{i}<x_{j} , \displaystyle f\left (x_{i} \right )>f\left (x_{j} \right ) .

Dacă funcţia \displaystyle f este strict monotonă, numărul de funcţii este egal cu numărul submulţimilor cu \displaystyle k elemente ale mulţimii \displaystyle B , deoarece valorile funcţiei nu pot fi aşezate decât într-un singur fel, fie în ordine crescătoare, fie în ordine descrescătoare.

Astfel, numărul de funcţii strict crescătoare este egal cu numărul de funcţii strict descrescătoare şi este egal cu \displaystyle C_{n}^{k} .

Numărul total de funcţii strict monotone (atât crescătoare, cât şi descrescătoare) este \displaystyle 2C_{n}^{k} .