Elemente de combinatorică. Permutări. Aranjamente. Combinări. Proprietăți

Aranjamente

Numarul submultimilor ordonate cu k elemente dintr-o multime cu n elemente este $A_{n}^{k}=\frac{n!}{\left( n-k \right)!}=n\cdot (n-1)\cdot ...\cdot (n-k+1)$ (aranjamente de n luate cate k ).

Combinari

 Numarul submultimilor cu k elemente dintr-o multime cu n elemente este $C_{n}^{k}=\frac{n!}{k!\left( n-k \right)!}=\frac{n\cdot (n-1)\cdot ...(n-k+1)}{k!}$ (combinari de n luate cate k )

Proprietati:

1. Formula combinarilor complementare: $C_{n}^{k}=C_{n}^{n-k};$
2. Formula de recurenta pentru combinari : $C_{n}^{k}+C_{n}^{k+1}=C_{n+1}^{k+1};$
3. $C_{n}^{0}+C_{n}^{1}+...+C_{n}^{n}={{2}^{n}}.$
4. $C_{n}^{0}+C_{n}^{2}+C_{n}^{4}+...=C_{n}^{1}+C_{n}^{3}+C_{n}^{5}+...={{2}^{n-1}}$
5. Daca $n\le m,$numarul functiilor injective f: A$\to$B este egal cu $A_{m}^{n}$
6. Daca m=n , numarul functiilor bijective f: A$\to$B este egal cu ${{P}_{n}}=n!$
7. Daca A,B$\subset \mathbb{R}$si $n\le m$, numarul functiilor strict crescatoare/ descrescatoare f: A$\to B$ este egal cu $C_{m}^{n}.$