ELEMENTE DE COMBINATORICA

ELEMENTE DE COMBINATORICA

Deseori suntem pusi in situatia de a evalua numarul unor grupari care se pot forma cu obiectele unei multimi date. Fie M o multime data, finita, cu elementele sale notate astfel: x₁, x₂, x₃, . , x_n. O grupare cu k elemente ale multimii M este o succesiune de k elemente, 1 k n, distincte sau nu. O grupare este caracterizata prin obiectele din care este formata si ordinea in care acestea sunt considerate. O grupare de trei elemente poate fi, de exemplu, urmatoarea:

(x₅, x₁, x₁₂).

Doua grupari, de exemplu (x₁, x₂, . , x_p) si (y₁, y₂, . , y_q), sunt identice daca si numai daca p=q si x_i = y_i pentru orice i = 1, 2, . , p. In cazul in care cel putin una din aceste conditii nu este indeplinita atunci gruparile se numesc distincte.

Permutari

Fie M o multime cu n elemente distincte, M = . Orice grupare cu n elemente distincte ale multimii M se numeste permutare asupra multimii M. Ca exemplu consideram multimea M cu elementele . Permutarile posibile ale elementelor acestei multimi sunt urmatoarele: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Gruparile cu trei elemente (2,1,2) sau (3,3,3) nu sunt permutari asupra multimii M deoarece elementele lor nu sunt distincte.

Numarul permutarilor asupra unei multimi cu n elemente distincte se noteaza cu P_n sau cu n! (se citeste 'n factorial') si este egal cu produsul tuturor numerelor naturale de la 1 la n.

Asadar,

P_n = n! = 1^.2^.3^. . ^.n (1.1)

Prin conventie se considera ca 0!

Una dintre cele mai utile proprietati legate de permutari este urmatoarea egalitate evidenta:

P_n+1 = (n+1)^.P_n (1.2)

Aranjamente

Fie M o multime de n elemente distincte, n 2. Gruparile cu k elemente distincte ale multimii M, 1 k n, se numesc aranjamente de n obiecte luate cate k. Numarul total al acestora se noteaza cu A^k_n si este dat de furmula

A^k_n = n^.(n-1)^.(n-2) ^. . ^.(n-k+1)

In formula (1.3) avem exact k factori. De exemplu, A = 10.9.8.7 = 5040. Daca consideram multimea M= numarul A =5.4=20 reprezinta numarul de aranjamente de 5 obiecte luate cate 2, iar acestea sunt

Cea mai utila formula legata de aranjamente este urmatoarea

A^k_n = n!/(n-k)!   

Se observa usor ca Aⁿ_n= n!, datorita conventiei mentionate anterior. De asemenea avem ca A _n = 1, in virtutea formulei (1.4).

Combinari

Atunci cand ne intereseaza grupari ale unui numar dat de obiecte in care ordinea obiectelor sa nu intereseze, spunem ca avem de-a face cu combinari ale acestora. Fie M o multime cu n elemente distincte. Combinarile de n obiecte luate cate k se noteaza cu C^k_n. Numarul total al acestora este dat de formula:

C^k_n = A^k_n / P_k = n! / [k!(n-k)!]

Luand acelasi exemplu de mai sus cu multimea M = , avem ca C^k_n = 10, iar acestea sunt: (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5).

Cea mai importanta proprietate a combinarilor este cea legata de complementareitate si este exprimata prin formula

C^k_n = C^n-k_n

Se observa usor ca C _n = Cⁿ_n

Binomul lui Newton

Se considera dezvoltarea binomiala cunoscuta sub numele de formula binomului lui Newton

(a b)ⁿ C _naⁿb⁰ C _na^n-1b¹ + C _na^n-2b²

+(-1)^kC^k_na^n-kb^k + . + (-1)ⁿCⁿ_na⁰bⁿ (1.7)

Coeficientii C _n, C _n, C _n, . , Cⁿ_n din aceasta dezvoltare se numesc coeficienti binomiali. Termenul general al dezvoltarii este dat de formula

T_k+1 = (-1)^kC^k_na^n-kb^k,    k=0,1,2, . ,n (1.8)