Elemente de combinatorică

Analiza combinatorică este un domeniu al matematicii care studiază modalitățile de numărare ale elementelor mulțimilor finite, precum și de alegere și aranjare a lor. Numeroase concepte specifice acestui domeniu intervin și în probleme de algoritmică.

Produsul cartezian

Fie $n\in \mathbb{N}$ și mulțimile $A_1$, $A_2$., …, $A_n$. Produsul cartezian $A_1\times A_2\times \dots \times A_n$ este mulțimea $n$-uplurilor $(x_1,x_2,\dots ,x_n)$ cu proprietatea că $x_1\in A_1$, $x_2\in A_2$, …, $x_n\in A_n$.

Regula produsului: Dacă mulțimile $A_1$, $A_2$., …, $A_n$ au respectiv $k_1$, $k_2$., …, $k_n$ atunci numărul de elemente al produsului cartezian $A_1\times A_2\times \dots \times A_n$ este $k_1\cdot k_2\cdot \dots \cdot k_n$.

Submulțimile unei multimi

Fie $A$ o mulțimi cu n elemente. Atunci ea are $2^n$ submulțimi:

Exemplu: Mulțimea $A=1,2,3$ are $2^3=8$ submulțimi:

1. $\mathrm{\varnothing }$
2. $\left\{1\right\}$, $\left\{2\right\}$, $\left\{3\right\}$
3. $\{1,2\}$, $\{1,3\}$, $\{2,3\}$
4. $\{1,2,3\}$

Permutări

Se numește permutare o corespondență biunivocă (bijecție) între o mulțime finită și ea însăși.

Altfel spus, se numește permutare a unei mulțimi finite o aranjare a elementelor sale într-o anumită ordine.

Exemplu: permutările mulțimii {1,2,3} sunt: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) și (3,2,1). Într-o altă reprezentare, acestea sunt:

$\left(\begin{array}{ccc}1& 2& 3\\ 1& 2& 3\end{array}\right)$, $\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$, $\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$, $\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$, $\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$, $\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$

Dacă $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$, atunci $\sigma (1)=3$, $\sigma (2)=1$ și $\sigma (3)=2$.

Numărul de permutări al unei mulțimi cu $n$ elemente este $P_n=n!=1\cdot 2\cdot \cdot \dots \cdot n$. Acest articol conține mai multe despre factorialul unui număr.

Numărul permutărilor unei mulțimi crește foarte repede. Pentru valori mici ale lui n, numărul permutărilor depășește domeniul de valori al datelor întregi, fiind necesară implementarea operațiilor pe numere mari.

Permutări cu repetiție

Considerăm un set de $n$ obiecte de $k$ tipuri. Avem $n_1$ obiecte de tipul 1, $n_2$ obiected e tipul 2, …, $n_k$ obiecte de tipul k și $n_1+n_2+\dots +n_k=n$. Numărul de permutări distincte ale celor n obiecte este:

$$P_R(n)=\frac{n!}{n_1!\cdot n_2!\cdot \dots \cdot n_k!}$$

Exemplu: Numărul de anagrame distincte ale cuvântului ABABA este:

$$P_R(2+3)=\frac{(2+3)!}{2!\cdot 3!}=\frac{1\cdot 2\cdot 3\cdot 4\cdot 5}{1\cdot 2\cdot 1\cdot 2\cdot 3}=10$$

Acestea sunt: AAABB, AABAB, AABBA, ABAAB, ABABA, ABBAA, BAAAB, BAABA, BABAA, BBAAA.

Aranjamente

Dacă A este o mulțime cu n elemente, submulțimile ordonate cu k elemente ale lui A, 0 ≤ k ≤ n se numesc aranjamente a n elemente luate câte k.

Numărul de aranjamente de $n$ luate câte $k$ se notează $A_n^k=n\cdot (n-1)\cdot (n-2)\cdot \dots \cdot (n-k+1)=\frac{n!}{(n-k)!}$.

La fel ca în cazul permutărilor, pentru determinarea numărului de aranjamente poate fi necesară implementarea operațiilor pe numere mari.

Combinări

Pentru o mulțime dată o combinare reprezintă o modalitate de alegere a unor elemente, fără a ține cont de ordinea lor. Se numesc combinări de k elemente submulțimile cu k elemente ale mulțimii, presupuse cu n elemente. Numărul de asemenea submulțimi se numește combinări de n luate câte k și se notează $C_n^k$.

Formule:

• $C_n^k=\frac{A_n^k}{P_k}$
• $C_n^k=\frac{n\cdot (n-1)\cdot \dots \cdot (n-k+1)}{1\cdot 2\cdot \dots \cdot k}$
• $C_n^k=\frac{n!}{k!\cdot (n-k)!}$
• $C_n^k=\{\begin{array}{ll}1& \text{dacă }k=0,\\ \frac{n–k+1}{k}\cdot C_n^k& \text{altfel}.\end{array}$
• $C_n^k=\{\begin{array}{ll}1& \text{dacă }n=k\text{ sau }k=0,\\ C_{n-1}^{k-1}+C_{n-1}^k& \text{altfel}.\end{array}$; această formulă se regăsește în Triunghiul lui Pascal

Numerele lui Catalan

Termenul general al acestui șir este:

$$C_n=C_{2n}^n–C_{2n}^{n+1}=\frac{1}{n+1}\cdot C_{2n}^n=\prod _{k=2}^n\frac{n+k}{k},\text{pentru }n\ge 0$$

O formulă recursivă:

$$C_{n+1}=\sum _{i=0}^n{C}_i\cdot C_{n-i}$$

Pentru $n=0,1,2,3,\dots$ numere Catalan sunt: $1,1,2,5,14,42,132,429,1430,4862,\dots$.

Există numeroase probleme care au ca rezultat numerele lui Catalan. Amintim:

• $C_n$ este egal cu numărul de șiruri de n paranteze deschise și n paranteze închise care se închid corect. Pentru n=3, avem $C_3=5$ variante: ((())), (())(), ()(()), ()()() și (()()).
• numărul de cuvinte Dyck de lungime 2*n: formate din n caractere X și n caractere Y și în orice prefix numărul de X este mai mare sau egal cu numărul de Y. Pentru n=3: XXXYYY, XXYYXY, XYXXYY, XYXYXY, XXYXYY.
• numărul de șiruri formate din n de 1 și n de -1 astfel încât toate sumele parțiale să fie nenegative.
• $C_n$ reprezintă numărul de modalități de a paranteza o expresie formată din n+1 operanzi ai unei operatii asociative: ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).
• $C_n$ reprezintă numărul de modalităti de a desena “șiruri de munți” cu n linii crescătoare și n linii descrescătoare. Munții încep și se termină la același nivel și nu coboară sub acel nivel:

                                            /\
           /\          /\       /\/\       /  \
/\/\/\    /  \/\    /\/  \     /    \     /    \

• numărul de drumuri laticiale de la punctul (0,0) la (2*n,0) cu pași din {(1,1),(1,-1) care nu coboară sub axa Ox.
• $C_n$ este numărul de modalități de a triangula un poligon cu n+2 laturi:

• $C_n$ este umărul de drumuri laticiale de la (0,0) la (n,n) cu pași din {(0,1),(1,0)} care nu depășesc prima diagonală $y=x$. Următoarea imagine conține drumurile pentru n=4:

• numărul de siruri $1⩽a_1⩽a_2⩽\dots ⩽a_n$ cu proprietatea că $a_k⩽k$ este $C_n$.
• $C_n$ numărul de modalități de a acoperi o scară cu n trepte folosind n dreptunghiuri. Pentru n=4:

• pe un cerc sunt 2*n puncte. Numărul posibilități de a desena n coarde care nu se intersectează este $C_n$.

Alte probleme care au care rezultat numărul lui Catalan sunt pe Wikipedia sau în documentul Exercises on Catalan and Related Numbers, Cambridge University Press, Richard P_ Stanley, June 1998.

Partițiile unei mulțimi

Fie $A=a_1,a_2,\dots ,a_n$ o mulțime (finită). Se numește partiție a mulțimii $A$ o familie de submulțimi $A_1,A_2,\dots ,A_k$ ale lui $A$ cu proprietățile:

1. $A_i\subseteq A$, $\mathrm{\forall }i=\overline{1,k}$
2. $A_1\cup A_2\cup \dots \cup A_k=A$
3. $A_i\cap A_j=\mathrm{\varnothing }$, $\mathrm{\forall }i\ne j$

De exemplu, $A=1,2,3$ are următoarele partiții:

• $1,2,3$
• $1,2,3$, $1,3,2$, $1,2,3$
• $1,2,3$

Numărul de partiții cu $k$ submulțimi ale unei mulțimi cu $n$ elemente se numește numărul lui Stirling de speța a doua, notat $S(n,k)$. El respectă următoarea relație de recurență:

$$\{\begin{array}{l}S(0,0)=1\\ S(0,n)=S(n,0)=0\\ S(n+1,k)=k\cdot S(n,k)+S(n,k-1)& \text{pentru }k>0\end{array}$$

Numerele Strirling de speța a doua pe Wikipedia

Numărul total de partiții ale unei mulțimi cu $n$ elemente este numărul lui Bell: $$B_n=\sum _{k=0}^{n}S(n,k)$$

Începând cu $B_0=B_1=1$, primele numere Bell sunt: $1,1,2,5,15,52,203,877,4140,\dots$.

Numerele Bell pot fi construite cu ajutorul așa-numitului triunghi Bell. Vom construi (parțial) un tablou A[][]:

• A[0][1] = 1
• primul element de pe liniile următoare este egal cu ultimul de pe linia precedentă: A[i][1] = A[i-1][i]
• celelalte elemente ale fiecărei linii sunt egale cu suma celor după elemnte din stânga (linia curentă și linia precedentă): A[i][j] = A[i][j-1] + A[i-1][j-1], pentru j=2,..., i+1
• primul elelemt de pe fiecare linie este numărul Bell corespunzător: Bn=A[n][1].

Numerele Bell pe Wikipedia

Citește mai departe