Analiză matematică/Analiză combinatorie/Exerciții

1) a) Să se determine numărul funcțiilor injective definite pe o mulțime cu $m$ elemente cu valori pe o mulțime cu $n$ elemente, unde $m,n\in \mathbb {N} ,\;m\leq n.$

b) Să se determine numărul aplicațiilor bijective ce pot fi definite pe o mulțime cu $n$ elemente.

R.

a) Fie mulțimile $A,B,\;|A|=m,|B|=n.$ Vom determina numărul aplicațiilor injective $f:A\to B.$ Din definiția injectivității, la argumente diferite $a_{i},a_{j}\in A,\;a_{i}\neq a_{j}$ se obțin imagini diferite: $f(a_{i})\neq f(a_{j}).$

Dacă $A=\{a_{1},a_{2},\cdots ,a_{m}\},$ unei funcții injective $f:A\to B$ îi corespunde o submulțime ordonată a lui $B$ și anume: $\left(f(a_{1}),f(a_{2}),\cdots ,f(a_{m})\right).$ Numărul submulțimilor ordonate cu $m$ elemente dintr-o mulțime cu $n$ elemente este $A_{n}^{m}$

Reciproc, fiecărui aranjament de $n$ elemente luate câte $m$ îi corespunde o unică aplicație injectivă $f:A\to B.$ Așadar, se poate stabili o corespondență bijectivă între mulțimea aplicațiilor injective $f:A\to B$ și mulțimea aranjamentelor de $n$ elemente luate câte $m.$ Deci numărul acestor funcții este $A_{n}^{m}.$

b) Se aplică punctul precedent pentru cazul particular $m=n,$ când orice aplicație injectivă este bijectivă și numărul căutat devine:

$A_{n}^{n}=n!.$

---

2) Să se demonstreze următoarele proprietăți ale combinărilor:

a)   $C_{n}^{k}=C_{n-1}^{k-1}+C_{n-2}^{k-1}+\cdots +C_{k-1}^{k-1};$

b)   $C_{n}^{0}C_{m}^{k}+C_{n}^{1}C_{m}^{k-1}+\cdots +C_{n}^{k}C_{m}^{0}=C_{m+n}^{k}.$