[10] Combinatorică - Probleme de bază

Postby **Admin** » 12 Jan 2013, 15:59

În topicul acesta vom încerca folosirea mai des a notaţiei uzuale folosită de elevi (începând cu clasa a 10-a) pentru combinări.

Adică vom folosi $C_n^k$ în loc de $\binom{n}{k}$ ... sau $C_3^2$ în loc de $\binom{3}{2}$

Reamintire a definiţiilor la cele 3 noţiuni de bază, folosindu-ne de notaţia : $n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot n$
(Prin definiţie $0! = 1$ )

1) Permutări : $P_n = n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot n$ şi reprezintă numărul total în care putem permuta $n$ obiecte (elemente).

De exemplu, dacă am avea $3$ obiecte notate cu $1, 2, 3$ (pentru simplitate) am avea permutările :

$123$
$132$
$213$
$231$
$312$
$321$

adică $6$ permutări şi observăm că : $6 = 3! = 1 \cdot 2 \cdot 3$

2) Combinări. Ca valoare : $C_n^k = \frac {n!}{k! \ (n-k)!}$ iar definiţia combinărilor este aşa : presupunând că avem o mulţime $X$ cu $n$ elemente atunci $C_n^k$ (unde $0 \leqslant k \leqslant n$ ) înseamnă numărul tuturor submulţimilor lui $X$ cu $k$ elemente.

De exemplu, pentru $C_3^2$ , dacă avem mulţimea $X = \{ 1, 2, 3 \}$ atunci

$\{ 1, 2 \}$
$\{ 1, 3 \}$
$\{ 2, 3 \}$

sunt cele $3$ submulţimi care au câte $2$ elemente .. şi se verifică uşor că : $C_3^2 = \frac {3!}{2! \ (3-2)!} = 3$

3) Aranjamente. Pentru simplitate, ca valoare $A_n^k = C_n^k \cdot P_k$ .
Provenienţă : Dacă avem o mulţime $X$ cu $n$ elemente iar $0 \leqslant k \leqslant n$ atunci $A_n^k$ reprezintă prin definiţie numărul tuturor submulţimilor ordonate cu câte $k$ elemente ale lui $X$ .
(Practic se iau ca şi la combinări toate submulţimile cu câte $k$ elemente, iar la fiecare din aceste submulţimi se iau toate permutările). Exemplificarea este relevantă: presupunem $X = \{1, 2, 3 \}$ atunci generăm toate aranjamentele de $3$ luate câte $2$ astfel :

$12$ şi $21$
$13$ şi $31$
$23$ şi $32$

deci toate cele $6$ aranjamente de $3$ luate câte $2$ .

iar $A_3^2 = 6 = 3 \cdot 2 = C_3^2 \cdot P_2$

Postby **Admin** » 12 Jan 2013, 17:17

$C_n^0 + C_n^1 + C_n^2 + ... + C_n^{n-1} + C_n^n = 2^n$

Folosim formula binomului lui Newton :

$(x+y)^n = C_n^0x^n + C_n^1x^{n-1}y + C_n^2x^{n-2}y^2 + ... + C_n^{n-1}xy^{n-1} + C_n^ny^n$ $= \sum_{k=0}^{n} C_n^kx^{n-k}y^k$
(ultima formă este restrânsă în sumă)

pentru $x=y=1$ şi obţinem $2^n = (1+1)^n =$ expresia iniţială

Postby **Admin** » 12 Jan 2013, 17:40

Problemă

$C_n^k = C_{n-1}^{k-1} + C_{n-2}^{k-1} + ... + C_{k}^{k-1} + C_{k-1}^{k-1}$

Rezolvare :

Fie $X = \{ 1, 2, 3, ... , n \}$ .

Toate cele $C_n^k$ de submulţimi ale lui $X$ care au $k$ elemente le vom enumera astfel :

# Toate submulţimile lui $X$ cu $k$ elemente care îl conţin obligatoriu pe $k$ şi nu au elemente mai mari decât $k$ .

Acestea sunt în număr de $C_{k-1}^{k-1}$ (este deci una singură şi e vorba de $\{1, 2, ... , k\}$ )

# Toate submulţimile lui $X$ cu $k$ elemente care îl conţin obligatoriu pe $k+1$ şi nu au elemente mai mari decât $k+1$ .

Acestea sunt în număr de $C_{k}^{k-1}$

...

# Toate submulţimile lui $X$ cu $k$ elemente care îl conţin obligatoriu pe $n-1$ şi nu au elemente mai mari decât $n-1$ .

Acestea sunt în număr de $C_{n-2}^{k-1}$

# Toate submulţimile lui $X$ cu $k$ elemente care îl conţin obligatoriu pe $n$ (şi evident nu au elemente mai mari decât $n$ ).

Acestea sunt în număr de $C_{n-1}^{k-1}$

Se observă cu uşurinţă că submulţimile luate mai sus sunt distincte şi ele reprezintă toate submulţimile lui $X$ care au câte $k$ elemente, deci concluzia problemei este evidentă prin sumare.