Elemente de combinatorica

1. Reguli generale ale combinatoricii

O multime împreuna cu o ordine bine determinata de dispunere a elementelor sale este o combinatie sau o multime ordonata.

Regula sumei

Daca  un anumit obiect A poate fi ales în m moduri, iar alt obiect B poate fi ales în n moduri, atunci alegerea lui A sau B poate fi realizata în (m + n) moduri.

Regula produsului

Daca  un anumit obiect A poate fi ales în m moduri s 151v2124b i daca dupa fiecare astfel de alegere, un obiect B se poate alege în n moduri, atunci alegerea perechii ( A;B ) în aceasta ordine poate fi realizata în (m · n) moduri.

2. Permutari. Aranjamente. Combinari

1. Permutari

Se considera o multime A cu n elemente, n N^*. Orice functie injectiva

f A se numeste permutare a multimii A.

L Notam numarul tuturor permutarilor multimi A cu P_n.

L Permutariile unei multimi cu n elemente pot fi gândite ca grupari de n elemente ale acestei multimi, astfel încât doua grupari difera una de cealalta prin ordinea elementelor.

L Notam n! = 1·2·3·...·n = si citim "n factorial"

L Prin conventie P₀ = 0! = 1.

L Fie propozitia P(n): "Numarul tuturor permutarilor multimii A cu n elemente este P_n = n! Pentru n = 1, propozitia este adevarata. Dorim sa aratam ca P_(n) implica P_(n+1). Fie A o multime cu n+1 elemente si fie f: A o functie injectiva. Observam ca f(n+1) poate fi ales oricare dintre cele n+1 elemente ale multimii A si o data fixat, celelalte elemente pot fi alese în n! moduri diferite, conform ipotezei. Astfel, stabilind pe rând pe fiecare element pentru f(n+1) vom obtine P_n+1 = ( n + 1 ) Pn

P_n = n!

LProprietati ale factorialului

1. P_n = n (n - 1) ( n - 2 ) ... ( n - k + 1) P_n-k , " k N, k ≤ n
2. P_n+1 = ( n + 1) P_n
3. k! · k = ( k + 1)! - k!
4. 
5. 
6. 

2. Aranjamente

Fie A o multime cu n elemente, n N^*, si fie k N^*, k ≤ n. Numin aranjament de n elemente luate câte k, k ≥ 1, ale multimii A, orice submultime ordonata de k elemente.

LO submultime ordonata a multimii A, formata din k elemente se descrie printr-o functie injectiva f: A.

LNotam cu numarul tuturor aranjamentelor de n elemente luate câte k.

LAranjamentele de n elemente luate câte k ( ale unei multimi de k elemente ) sunt grupari de k elemente astfel încât doua grupari difera fie prin natura elementelor, fie prin ordinea lor.

LFie A o multime cu n elemente, n N^*, si fie k N, k ≤ n, fixat. Numarul tuturor aranjamentelor din A, de n elemente luate câte k, este: 

LProprietati ale aranjamentelor:

3. Combinari

Fie A o multime cu n elemente, n N^*, si fie k N, k ≤ n. Numim combinare de n elemente luate câte k orice submultime cu k elemente a multimii A.

L Numarul tuturor combinarilor de n elemente luate câte k se noateaza cu .

L Combinarile de n elemente luate de k, ale unei multimi cu n elemente, pot fi gândite ca grupari de k elemente, dintre cele n elemente ale multimii initiale, astfel încât doua grupari difera numai prin natura elementelor.

L Fie A o multime cu n elemente, n N^*, fie k N, k ≤ n, fixat. Atunci, numarul tuturor combinatiilor de n elemente luate câte k este:

LCombinarile le putem gasi în triunghiul lui Pascal:

LProprietati ale combinarilor

3. Binomul lui Newton

Fie a si b doua numere reale si n N . Atunci este adevarata egalitatea:

LAstfel, putem redefini combinarile ca fiind coeficientii binomului lui Newton! Totusi, ei pot fi diferiti de coeficientii dezvoltarii. De exemplu pentru ( 2a + b )² = 4a² + 4ab + b², 4,4,1 sunt coeficientii dezvoltarii, iar 1,2,1 sunt coeficientii binomiali. Coeficientii binomiali se regasesc pe rândul n + 1 in triunghiul lui Pascal.

LTermenul general al dezvoltarii este: , unde 0 ≤ k ≤ n

4. Calculul unor sume cu combinari

Suma:

Principiu de rezolvare:

Suma:

Principiu de rezolvare:

Suma: , m, n N, k  ≤ n, k ≤ m

Principiu de rezolvare:

Observam ca suma este coeficientul binamiol a lui x^k din dezvoltarea ( 1 + x )ⁿ · ( 1 + x )^m

= ( 1 + x )^m+n

particularizare

Suma

Principiu de rezolvare:

notam cu si )