16 Definiții pentru combinatorică disponibile

Regula produsului în probleme de numărare stabilește că dacă avem $n$ evenimente independente, fiecare cu $k_i$ posibilități, numărul total de rezultate posibile este produsul $k_1 \cdot k_2 \cdot ... \cdot k_n$. Aceasta se aplică în special la probleme de numărare și combinatorică.

Factorialul este o operație matematică definită astfel: 1. Pentru $n > 0$: $n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot n$ 2. Prin convenție: $0! = 1$ Factorialul se folosește frecvent în combinatorică și teoria probabilităților.

Numărul de permutări $P_n$ pentru o mulțime cu $n$ elemente este dat de formula:
$P_n = n!$
Aceasta reprezintă numărul total de moduri în care se pot aranja $n$ elemente distincte. Factorialul $n!$ crește foarte rapid odată cu creșterea lui $n$.

Numărul de aranjamente $A_n^k$ de $k$ elemente dintr-o mulțime de $n$ elemente este:
$A_n^k = \frac{n!}{(n-k)!}, \quad 0 \leq k \leq n$
Aceasta reprezintă numărul de moduri de a selecta și ordona $k$ elemente din $n$.

Numărul de combinări $C_n^k$ de $k$ elemente dintr-o mulțime de $n$ elemente este:
$C_n^k = \frac{n!}{k!(n-k)!}, \quad 0 \leq k \leq n$
Aceasta reprezintă numărul de moduri de a selecta $k$ elemente din $n$, fără a ține cont de ordine.

Formula combinărilor complementare $C_n^k = C_n^{n-k}$ arată că:
Numărul de moduri de a alege $k$ elemente dintr-o mulțime de $n$ elemente este egal cu numărul de moduri de a alege $n-k$ elemente din aceeași mulțime. Aceasta reflectă simetria în selecția de elemente.

Formula de recurență pentru combinări este:
$C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$
Aceasta formează baza triunghiului lui Pascal și arată cum fiecare număr este suma celor două numere de deasupra sa în triunghi.

Binomul lui Newton exprimă dezvoltarea $(a+b)^n$ ca:
$(a+b)^n = \sum_{k=0}^n C_n^k \cdot a^{n-k} \cdot b^k$
Aceasta arată cum se poate expanda puterea unui binom în termeni de coeficienți binomiali și puteri ale $a$ și $b$.

Termenul general (de rang $k+1$) în dezvoltarea binomului lui Newton $(a+b)^n$ este:
$T_{k+1} = C_n^k \cdot a^{n-k} \cdot b^k$
Aceasta arată structura fiecărui termen în expansiune, combinând coeficienții binomiali cu puterile lui $a$ și $b$.

Coeficienții binomiali în $(a+b)^n$ sunt $C_n^0, C_n^1, C_n^2, ..., C_n^n$. Suma lor este $2^n$, ceea ce rezultă din dezvoltarea $(1+1)^n$. Acești coeficienți formează rândul $n$ din triunghiul lui Pascal.

În dezvoltarea binomului lui Newton:
1. Suma coeficienților de rang impar = Suma coeficienților de rang par
2. Valoarea comună a acestor sume este $2^{n-1}$
Aceasta rezultă din dezvoltarea $(1+1)^n$ și $(1-1)^n$.

Formula de recurență între termeni consecutivi în $(a+b)^n$ este:
$\frac{T_{k+2}}{T_{k+1}} = \frac{n-k}{k+1} \cdot \frac{b}{a}$ sau
$\frac{T_{k+1}}{T_k} = \frac{n-k+1}{k} \cdot \frac{b}{a}$
Aceasta permite calculul eficient al termenilor succesivi.

O permutare de ordin n este o funcție bijectivă $\sigma: A \rightarrow A$, unde $A = \{1, 2, ..., n\}$. Se notează:
$\sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}$
Multimea tuturor permutărilor de ordin n se notează $S_n$, cu $\text{card}(S_n) = n!$

Semnul unei permutări $\sigma$, notat $\varepsilon(\sigma)$, se calculează astfel:
1. Identifică inversiunile: perechi $(i,j)$ cu $i < j$ și $\sigma(i)>\sigma(j)$
2. Numără inversiunile: $m(\sigma)$
3. Calculează semnul: $\varepsilon(\sigma) = (-1)^{m(\sigma)}$
O permutare este pară dacă $\varepsilon(\sigma)=+1$, impară dacă $\varepsilon(\sigma)=-1$.

Proprietățile permutărilor în funcție de semn sunt:
1. Pară: semnul este $+1$; Impară: semnul este $-1$
2. Semnul produsului: $\varepsilon(\sigma_1\sigma_2) = \varepsilon(\sigma_1)\varepsilon(\sigma_2)$
Aceste proprietăți sunt fundamentale în teoria grupurilor și în studiul simetriilor.

$S_n$ este mulțimea tuturor permutărilor de ordin $n$. Proprietăți:
1. card $S_n$ = $n!$
2. $n! = n × (n-1) × (n-2) × ... × 2 × 1$
Această mulțime formează un grup simetric de ordin n, fundamental în algebra abstractă și teoria grupurilor.