Elemente de combinatorică: Permutări, Aranjamente, Combinări

Elemente de combinatorică: Permutări, Aranjamente, Combinări

Combinatorica este ramura matematicii care se ocupă în principal de numărarea modurilor în care pot fi alese anumite obiecte, respectând anumite condiții. În acest articol voi prezenta cele trei elemente de bază ale combinatoricii, precum și câteva aplicații ale acestora. Pentru simplitate, ne vom referi doar la mulțimi finite de forma M={1,2,,n}M = \{1, 2, \ldots, n\} cu nNn \in \mathbb{N} Dar mai întâi trebuie să amintesc cele două reguli fundamentale folosite în problemele de numărare:

Regula sumei

Dacă avem două mulțimi disjuncte AA și BB cu mm și respectiv nn elemente, numărul de moduri de a alege un element din AA sau din BB este m+nm + n Cu alte cuvinte, reuniunea mulțimilor AA și BB are m+nm + n elemente.

Regula produsului

Dacă avem două mulțimi AA și BB cu mm și respectiv nn elemente, numărul de moduri de a alege un element din AA și unul din BB este mnm \cdot n Cu alte cuvinte, produsul cartezian al mulțimilor AA și BB are mnm \cdot n elemente.

Permutări

Din punct de vedere combinatorial, o permutare a unei mulțimi reprezintă o modalitate de a aranja secvențial elementele acesteia. De exemplu, permutările mulțimii A={1,2,3}A = \{1, 2, 3\} sunt:

(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1) (1, 2, 3)\\ (1, 3, 2)\\ (2, 1, 3)\\ (2, 3, 1)\\ (3, 1, 2)\\ (3, 2, 1)

Permutările unei mulțimi AA pot fi privite de asemenea drept totalitatea funcțiilor bijective definite pe AA cu valori în AA Asta e ușor de înțeles dacă ne gândim că f(x)f(x) nu trebuie să fie neapărat o expresie ce-l conține pe xx ci îl putem defini folosind o înșiruire de pentru-uri. De exemplu, a treia permutare de mai sus reprezintă funcția:

f:AA,f(x)={2, pentru x=11, pentru x=23, pentru x=3f : A \rightarrow A, f(x) = \begin{cases} 2 \text{, pentru } x = 1\\ 1 \text{, pentru } x = 2\\ 3 \text{, pentru } x = 3 \end{cases}

Numărul permutărilor de ordin nn (permutările unei mulțimi AA cu nn elemente) se notează cu PnP_n și este egal cu n!n! (Amintesc că n!n! se citește nn factorial și este egal cu 123n1 \cdot 2 \cdot 3 \cdots n Această relație poate fi demonstrată în mai multe moduri. Să analizăm două dintre ele:

Metoda 1

Atunci când vrem să construim o permutare de ordin nn pe prima poziție putem pune orice valoare de la 11 la nn deci avem nn variante. Pentru a doua poziție, ne-au rămas n1n - 1 variante, pentru că deja am folosit una dintre valori pentru prima poziție. Pentru a treia poziție, am rămas cu n2n - 2 variante, pentru că deja am folosit două elemente pentru primele două poziții. Generalizând raționamentul, pentru poziția ii (1in\htmlClass{katexified}{(} 1 \le i \le n avem ni+1n - i + 1 variante rămase. Aplicând regula produsului, obținem:

Pn=n(n1)(n2)1=n!P_n = n \cdot (n - 1) \cdot (n - 2) \cdots 1 = n!

Metoda 2

Vom demonstra prin inducție matematică relația Pn=n!P_n = n! Dacă avem o permutare de ordin kk și vrem să obținem din aceasta una de ordin k+1k + 1 nu avem decât să inserăm undeva în ea valoarea k+1k + 1 Aceasta poate fi inserată înainte de o poziție ii cu 1ik1 \le i \le k sau după ultima poziție. În total avem k+1k + 1 poziții posibile pentru noul element. Conform regulii produsului, obținem Pk+1=(k+1)PkP_{k + 1} = (k + 1) \cdot P_k de unde Pn=n!P_n = n!

Permutări cu repetiție

Când vine vorba să numărăm permutările unui șir ale cărui elemente nu sunt neapărat distincte, formula clasică de la permutări nu mai funcționează. De exemplu, pe o permutare de genul 1,3,2,3\langle 1, 3, 2, 3 \rangle am număra-o de două ori, ca și cum cei doi de 33 ar fi numere diferite. O dată cu primul 33 pe poziția 22 și al doilea 33 pe poziția 44 și o dată cu al doilea 33 pe poziția 22 și primul 33 pe poziția 44

Deci, dacă notăm cu f(i)f(i) frecvența (numărul de apariții al) numărului ii în permutare, atunci pentru fiecare ii din șirul aa am numărat de Pf(i)P_{f(i)} ori mai multe permutări decât trebuia. Așadar, formula pentru numărul de permutări cu repetiție ale unui șir aa de lungime nn cu elementele mai mici sau egale cu nn este:

PR(n)=n!f(1)!f(2)!f(3)!f(n)!P_R(n) = \frac{n!}{f(1)! \cdot f(2)! \cdot f(3)! \cdots f(n)!}

Aranjamente

Un aranjament de nn elemente luate câte kk al mulțimii AA de cardinal nn reprezintă o submulțime ordonată a lui AA de kk elemente. De exemplu, aranjamentele de 33 luate câte 22 ale mulțimii A={1,2,3}A = \{1, 2, 3\} sunt:

(1,2)(1,3)(2,1)(2,3)(3,1)(3,2) (1, 2)\\ (1, 3)\\ (2, 1)\\ (2, 3)\\ (3, 1)\\ (3, 2)

Similar permutărilor, aranjamentele pot fi considerate funcții injective definite pe mulțimea {1,2,,k}\{1, 2, \ldots, k\} cu valori în {1,2,,n}\{1, 2, \ldots, n\} Semnificația expresiei f(x)=yf(x) = y este că elementul de pe poziția xx din aranjament este egal cu yy Cred că deja e clar că permutările sunt un caz particular de aranjamente: Permutările de ordin nn sunt aranjamente de nn luate câte nn

Numărul aranjamentelor de nn luate câte kk se notează cu AnkA_n^k și este egal cu n!(nk)!\frac{n!}{(n - k)!} Din nou, putem demonstra această relație în două moduri:

Metoda 1

Atunci când construim un aranjament de nn elemente luate câte kk pe prima poziție putem pune orice valoare, deci avem nn variante. Pe a doua poziție putem pune orice valoare, mai puțin cea pe care deja am folosit-o, deci am rămas cu n1n - 1 variante. Generalizând, obținem:

Ank=n(n1)(n2)(nk+1)=n!(nk)!A_n^k = n \cdot (n - 1) \cdot (n - 2) \cdots (n - k + 1) = \frac{n!}{(n - k)!}

Metoda 2

Putem construi aranjamentele de nn elemente luate câte kk pornind de la permutările de ordin nn Pentru asta, este de ajuns să ștergem ultimele nkn - k elemente din fiecare permutare, însă nu vom rămâne cu aranjamente distincte. De exemplu, dacă n=5n = 5 și k=2k = 2 permutările care se transformă în aranjamentul (3,1)(3, 1) sunt:

(3,1,2,4,5)(3,1,2,5,4)(3,1,4,2,5)(3,1,4,5,2)(3,1,5,2,4)(3,1,5,4,2) (\textbf{3}, \textbf{1}, 2, 4, 5)\\ (\textbf{3}, \textbf{1}, 2, 5, 4)\\ (\textbf{3}, \textbf{1}, 4, 2, 5)\\ (\textbf{3}, \textbf{1}, 4, 5, 2)\\ (\textbf{3}, \textbf{1}, 5, 2, 4)\\ (\textbf{3}, \textbf{1}, 5, 4, 2)

Se observă ușor că numărul de permutări care generează un anumit aranjament este PnkP_{n - k} pentru că ultimele nkn - k elemente ale lor pot fi aranjate în PnkP_{n - k} moduri. Așadar, Ank=PnPnk=n!(nk)!A_n^k = \frac{P_n}{P_{n - k}} = \frac{n!}{(n - k)!}

Combinări

Combinările de nn elemente luate câte kk ale mulțimii AA de cardinal nn reprezintă submulțimile cu kk elemente ale lui AA De remarcat că submulțimile nu sunt ordonate, ceea ce înseamnă că, în cazul combinărilor, submulțimile {1,2,3}\{1, 2, 3\} și {2,3,1}\{2, 3, 1\} nu sunt diferite. De exemplu, combinările de 44 luate câte 33 ale mulțimii A={1,2,3,4}A = \{1, 2, 3, 4\} sunt:

{1,2,3}{1,2,4}{1,3,4}{2,3,4} \{1, 2, 3\}\\ \{1, 2, 4\}\\ \{1, 3, 4\}\\ \{2, 3, 4\}

Numărul de combinări de nn luate câte kk se notează cu CnkC_n^k și este egal cu n!k!(nk)!\frac{n!}{k!(n - k)!} Demonstrația este următoarea: Diferența dintre aranjamente și combinări este că aranjamentele sunt submulțimi ordonate. Deci, o combinare de lungime kk corespunde aranjamentelor de lungime kk formate permutând elementele respectivei combinări. Numărul acelor permutări este PkP_k de unde Cnk=AnkPk=n!k!(nk)!C_n^k = \frac{A_n^k}{P_k} = \frac{n!}{k!(n - k)!}

Cum combinările numără submulțimile unei mulțimi în funcție de cardinalul lor, suma combinărilor de nn luate câte kk cu 0kn0 \le k \le n este egală cu numărul total de submulțimi ale unei mulțimi de cardinal nn Acesta este 2n2^n deoarece pe fiecare element putem fie să-l luăm, fie să nu-l luăm în cadrul submulțimii, așa că pentru fiecare element avem două variante. Aplicând regula produsului, obținem 222de n ori=2n\underbrace{2 \cdot 2 \cdots 2}_{\text{de } n \text{ ori}} = 2^n

Triunghiul lui Pascal

Triunghiul lui Pascal se referă la aranjamentul geometric pe care-l obținem când scriem pe fiecare linie n0n \ge 0 numerele CnkC_n^k unde kk ia valori pe rând de la 00 la nn

Triunghiul lui Pascal

Acest desen ne ajută să vizualizăm mai ușor diverse proprietăți ale combinărilor. De exemplu, dacă colorăm cu gri combinările pare, obținem Triunghiul lui Sierpinski, ceea ce am ilustrat și în desenul de mai sus. O altă observație este că Cnk=CnnkC_n^k = C_n^{n - k} Poate fi demonstrată imediat folosind formula cu factoriale: n!k!(nk)!=n!(nk)!k!\frac{n!}{k!(n - k)!} = \frac{n!}{(n - k)!k!}

Poate cea mai importantă proprietate a combinărilor ce rezultă din Triunghiul lui Pascal este următoarea relație de recurență:

Cnk=Cn1k1+Cn1kC_n^k = C_{n - 1}^{k - 1} + C_{n - 1}^k

Ea ne permite să precalculăm toate combinările până la linia nn în O(n2)O(n^2) – complexitate, evident, optimă, fiind egală cu dimensiunea output-ului:

comb[0][0] = 1;
for (int i = 1; i <= n; i++) {
comb[i][0] = 1;
for (int j = 1; j <= i; j++)
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}

Recurența poate fi demonstrată relativ ușor folosind din nou formula cu factoriale:

n!k!(nk)!=(n1)!(k1)!(nk)!+(n1)!k!(nk1)!nk!(nk)!=1(k1)!(nk)!+1k!(nk1)!n(nk)!=k(nk)!+1(nk1)!n=k+nk\begin{align*} \frac{n!}{k!(n - k)!} &= \frac{(n - 1)!}{(k - 1)!(n - k)!} + \frac{(n - 1)!}{k!(n - k - 1)!}\\ \frac{n}{k!(n - k)!} &= \frac{1}{(k - 1)!(n - k)!} + \frac{1}{k!(n - k - 1)!}\\ \frac{n}{(n - k)!} &= \frac{k}{(n - k)!} + \frac{1}{(n - k - 1)!}\\ n &= k + n - k \end{align*}

Însă nu e o metodă suficient de interesantă sau de ușoară la calcule. O prefer pe cea constructivă, pentru că ne obișnuiește cu gândirea specifică problemelor de programare dinamică: Fie mulțimile A={1,2,,n}A = \{1, 2, \ldots, n\} și B={1,2,,n1}B = \{1, 2, \ldots, n - 1\} Putem construi o combinare a lui AA de kk elemente, adăugându-l pe nn la o combinare de k1k - 1 elemente a mulțimii BB Însă, nu toate combinările trebuie sa-l conțină pe nn Observăm că cele din urmă sunt combinări de kk elemente ale lui BB Cum cele două tipuri de combinări menționate sunt numărate de Cn1k1C_{n - 1}^{k - 1} și respectiv de Cn1kC_{n - 1}^{k} aplicând regula sumei, obținem recurența ce trebuia demonstrată.

O altă formulă ce poate fi dedusă din Triunghiul lui Pascal este aceasta:

Cnk=Cn1k1+Cn2k1+Cn3k1++Ck1k1C_n^k = C_{n - 1}^{k - 1} + C_{n - 2}^{k - 1} + C_{n - 3}^{k - 1} + \cdots + C_{k - 1}^{k - 1}

Și se demonstrează așa:

Cnk=Cn1k1+Cn1kCnk=Cn1k1+Cn2k1+Cn2kCnk=Cn1k1+Cn2k1+Cn3k1+Cn3k  Cnk=Cn1k1+Cn2k1+Cn3k1++Ck+1kCnk=Cn1k1+Cn2k1+Cn3k1++Ckk1+CkkCnk=Cn1k1+Cn2k1+Cn3k1++Ckk1+Ck1k1\begin{align*} C_n^k &= C_{n - 1}^{k - 1} + C_{n - 1}^k\\ C_n^k &= C_{n - 1}^{k - 1} + C_{n - 2}^{k - 1} + C_{n - 2}^k\\ C_n^k &= C_{n - 1}^{k - 1} + C_{n - 2}^{k - 1} + C_{n - 3}^{k - 1} + C_{n - 3}^k\\ &\text{ }\text{ }\vdots\\ C_n^k &= C_{n - 1}^{k - 1} + C_{n - 2}^{k - 1} + C_{n - 3}^{k - 1} + \cdots + C_{k + 1}^k\\ C_n^k &= C_{n - 1}^{k - 1} + C_{n - 2}^{k - 1} + C_{n - 3}^{k - 1} + \cdots + C_k^{k - 1} + C_k^k\\ C_n^k &= C_{n - 1}^{k - 1} + C_{n - 2}^{k - 1} + C_{n - 3}^{k - 1} + \cdots + C_k^{k - 1} + C_{k - 1}^{k - 1} \end{align*}

Nu știu cât de utilă pare, dar eu chiar am avut nevoie de ea la un moment dat într-o problemă.

Binomul lui Newton

Combinările se mai numesc coeficienți binomiali, deoarece se regăsesc drept coeficienți în descompunerea lui (a+b)n(a + b)^n (nN\htmlClass{katexified}{(} n \in \mathbb{N} numit Binomul lui Newton:

(a+b)n=Cn0anb0+Cn1an1b1+Cn2an2b2++Cnna0bn(a + b)^n = C_n^0 a^n b^0 + C_n^1 a^{n - 1} b^1 + C_n^2 a^{n - 2} b^2 + \cdots + C_n^n a^0 b^n

În ciuda aparențelor, Binomul lui Newton este util și la informatică! L-am folosit odată la problema Scara2 pentru a demonstra că dinamica avea de fapt complexitatea 3n3^n și nu 4n4^n cum credeam inițial.

Demonstrația formulei se bazează pe inducție: Presupunem că (a+b)n(a + b)^n are forma de mai sus și demonstrăm că, înmulțind expresia cu a+ba + b obținem o descompunere de aceeași formă:

(a+b)n+1=Cn0an+1b0+Cn1anb1+Cn2an1b2++Cnna1bn+Cn0anb1+Cn1an1b2++Cnn1a1bn+Cnna0bn+1\begin{align*} (a + b)^{n + 1} &= C_n^0 a^{n + 1} b^0 + \textcolor{dodgerblue}{C_n^1 a^n b^1} + \textcolor{limegreen}{C_n^2 a^{n - 1} b^2} + \cdots + \textcolor{orangered}{C_n^n a^1 b^n}\\ &+ \textcolor{dodgerblue}{C_n^0 a^n b^1} + \textcolor{limegreen}{C_n^1 a^{n - 1} b^2} + \cdots + \textcolor{orangered}{C_n^{n - 1} a^1 b^n} + C_n^n a^0 b^{n + 1} \end{align*}

Grupăm termenii asemenea, aplicăm coeficienților acestora formula de recurență a combinărilor și înlocuim Cn0C_n^0 cu Cn+10C_{n + 1}^0 și CnnC_n^n cu Cn+1n+1C_{n + 1}^{n + 1} căci toate sunt egale cu 11

(a+b)n+1=Cn0an+1b0+(Cn1+Cn0)anb1+(Cn2+Cn1)an1b2++(Cnn+Cnn1)a1bn+Cnna0bn+1(a+b)n+1=Cn+10an+1b0+Cn+11anb1+Cn+12an1b2++Cn+1na1bn+Cn+1n+1a0bn+1\small \begin{align*} (a + b)^{n + 1} &= C_n^0 a^{n + 1} b^0 + \textcolor{dodgerblue}{(C_n^1 + C_n^0) a^n b^1} + \textcolor{limegreen}{(C_n^2 + C_n^1) a^{n - 1} b^2} + \cdots + \textcolor{orangered}{(C_n^n + C_n^{n - 1}) a^1 b^n} + C_n^n a^0 b^{n + 1}\\ (a + b)^{n + 1} &= C_{n + 1}^0 a^{n + 1} b^0 + \textcolor{dodgerblue}{C_{n + 1}^1 a^n b^1} + \textcolor{limegreen}{C_{n + 1}^2 a^{n - 1} b^2} + \cdots + \textcolor{orangered}{C_{n + 1}^n a^1 b^n} + C_{n + 1}^{n + 1} a^0 b^{n + 1} \end{align*}

Notă: Prin convenție, 0!=P0=An0=Cn0=10! = P_0 = A_n^0 = C_n^0 = 1 unde nNn \in \mathbb{N} Cea mai simplă explicație este că 11 e elementul neutru la înmulțire. Iar în lipsa acestei convenții, formulele n-ar mai funcționa.


Cam atât despre permutări, aranjamente și combinări. Urmează în curând un articol despre numărul partițiilor unui număr natural! Dacă aveți vreo întrebare despre combinatorică, nu ezitați să o lăsați mai jos, într-un comentariu

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii