Analiză matematică/Analiză combinatorie

Analiza combinatorie este un domeniu al matematicii discrete care studiază modalitățile de numărare ale elementelor mulțimilor finite. Importanța acesteia în cadrul analizei matematice constă în special în faptul că furnizează valorile coeficienților (coeficienți binomiali) care apar în ridicarea la putere a polinoamelor.

Combinări

Fie $A$ o mulțime conținând $n$ elemente, $n\in \mathbb {N}$. O submulțime a acesteia conținând $p$ elemente, $k\in \mathbb {N} ,p\leq n,$ se numește combinare de $k$ elemente din $A.$ Se poate demonstra că numărul acestor combinări este:

$C_{n}^{k}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{p!}}={\frac {n!}{k!(n-k)!}}.$

(combinări de n elemente luate câte k)

În cazul în care aceste submulțimi sunt considerate ordonate, numărul acestora se numește aranjamente:

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

Formula lui Pascal

Fie $n,k\in \mathbb {N} ^{*}$ cu $k\leq n.$ Există relația:

$C_{n}^{k}=C_{n-1}^{k}+C_{n-1}^{k-1}.$   (Formula lui Pascal)

Demonstrație. Fie o mulțime $A$ cu $n$ elemente. Să presupunem că am extras din mulțime o submulțime cu $k$ elemente. Să considerăm elementul $a\in A.$ Dacă acesta aparține combinării, celelalte $k-1$ elemente rămase formează o sumbmulțime a lui $A\setminus \{a\}$ de cardinal $n-1.$ Dacă elementul $a$ nu aparține combinării, atunci sunt $k$ elemente care formează submulțimea lui $A\setminus \{a\}.$ Deoarece avem de-a face cu o reuniune de mulțimi disjuncte, se face suma cardinalilor și se ajunge la relația de demonstrat.

Formula de mai sus permite așezarea combinărilor în ceea ce se numește triunghiul lui Pascal:

${\begin{matrix}&&&C_{0}^{0}&&&\\&&C_{1}^{0}&&C_{1}^{1}&&\\&C_{2}^{0}&&C_{2}^{1}&&C_{2}^{2}&\\C_{3}^{0}&&C_{3}^{1}&&C_{3}^{2}&&C_{3}^{3}\\\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\end{matrix}}$

${\begin{matrix}&&&1&&&\\&&1&&1&&\\&1&&2&&1&\\1&&3&&3&&1\\\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\end{matrix}}$

unde fiecare combinare este suma celor două situate deasupra sa.