Formule: Combinatorică

Numeri fără să enumeri: factorial, permutări, aranjamente, combinări și binomul lui Newton. 10 formule, clasa 10.

Regula produsului și regula sumei — clasa 10

ș i \Rightarrow n_{1} \cdot n_{2} \cdot \dots \cdot n_{k}, sau \Rightarrow n_{1} + n_{2} + \dots + n_{k}

$n_{1}, n_{2}, \dots, n_{k}$ sunt numerele de variante de la fiecare pas, respectiv de la fiecare situație. Regula produsului se folosește când alegerea se face în etape care au loc toate („și… și…”): variantele se înmulțesc. Regula sumei se folosește când situațiile se exclud între ele („sau… sau…”), fără nicio suprapunere: variantele se adună. Capcană: întrebarea „și” sau „sau”? se pune înaintea oricărui calcul, iar la regula sumei cazurile trebuie să fie disjuncte, altfel numeri de două ori.

Exemplu: La cantină sunt $3$ supe și $4$ feluri principale. Un meniu complet (supă și fel principal) se alcătuiește în $3 \cdot 4 = 12$ moduri. • Dacă iei un singur fel, supă sau fel principal, ai $3 + 4 = 7$ variante. • Un cod format din $2$ litere alese din ${A, B, C}$ , urmate de o cifră, se poate scrie în $3 \cdot 3 \cdot 10 = 90$ moduri.

Factorialul unui număr natural — clasa 10

n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n, 0! = 1, n! = n \cdot (n - 1)!

$n!$ (citit „ $n$ factorial”) este produsul tuturor numerelor naturale de la $1$ la $n$ . Convenția $0! = 1$ nu este o toană: ea păstrează valabilă recurența $n! = n \cdot (n - 1)!$ și pentru $n = 1$ . Factorialul crește amețitor de repede: $1$ , $1$ , $2$ , $6$ , $24$ , $120$ , $720$ , $5040$ , $40320$ . Capcană: nu calcula niciodată factorialele mari, ci simplifică raportul — $\frac{n !}{( n - k )!} = n (n - 1) \dots (n - k + 1)$ are exact $k$ factori.

Exemplu: $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$ și $8! = 40320$ . • $\frac{10 !}{8 !} = 10 \cdot 9 = 90$ , fără să calculezi $10!$ . • $\frac{( n + 1 )!}{n !} = n + 1$ .

Permutări — clasa 10

P_{n} = n!

O permutare a unei mulțimi cu $n$ elemente este o așezare a tuturor elementelor într-o ordine, fiecare apărând exact o dată; $P_{n}$ numără toate așezările posibile. Formula iese din regula produsului: $n$ variante pentru primul loc, $n - 1$ pentru al doilea și tot așa, până la $1$ . Trei criterii de recunoaștere: folosești toate elementele, ordinea contează, elementele sunt distincte. Dacă unul dintre ele cade, problema cere altă metodă. Convenție: $P_{0} = 1$ .

Exemplu: $P_{5} = 5! = 120$ : cuvântul CARTE, cu $5$ litere distincte, are $120$ de anagrame. • $7$ persoane se așază pe $7$ scaune în $P_{7} = 5040$ de moduri. • Dacă două dintre ele trebuie să stea alături, le legi într-un bloc: $P_{6} \cdot P_{2} = 720 \cdot 2 = 1440$ de moduri.

Aranjamente — clasa 10

A_{n}^{k} = \frac{n !}{( n - k )!} = n (n - 1) \dots (n - k + 1), 0 \leq k \leq n

Un aranjament de $n$ luate câte $k$ este o alegere ordonată de $k$ elemente distincte dintre cele $n$ : se folosesc doar $k$ dintre ele, iar ordinea contează. Forma-produs are exact $k$ factori, primul $n$ și ultimul $n - k + 1$ — este cea mai rapidă la calcule numerice; forma cu factoriale e potrivită la simplificări cu literă. Cazuri utile: $A_{n}^{0} = 1$ , $A_{n}^{1} = n$ , $A_{n}^{n} = n! = P_{n}$ . Criteriu de recunoaștere: dacă schimbând între ele două dintre elementele alese obții altă situație, este aranjament.

Exemplu: $A_{5}^{3} = 5 \cdot 4 \cdot 3 = 60$ : un steag cu $3$ benzi de culori diferite, alese dintre $5$ culori, se poate face în $60$ de feluri. • $A_{10}^{2} = 10 \cdot 9 = 90$ : atâtea moduri sunt de a alege un președinte și un vicepreședinte dintr-un grup de $10$ elevi. • $A_{6}^{6} = 6! = 720$ .

Combinări — clasa 10

C_{n}^{k} = \frac{A _{n}^{k}}{k !} = \frac{n !}{k ! ( n - k )!}, 0 \leq k \leq n

O combinare de $n$ luate câte $k$ este o submulțime cu $k$ elemente: ordinea nu contează, elementele nu se repetă. Legătura cu aranjamentele este $A_{n}^{k} = k! \cdot C_{n}^{k}$ , pentru că fiecare submulțime poate fi ordonată în $k!$ feluri. Cazuri de memorat: $C_{n}^{0} = C_{n}^{n} = 1$ , $C_{n}^{1} = C_{n}^{n - 1} = n$ , $C_{n}^{2} = \frac{n ( n - 1 )}{2}$ . Criteriul de decizie: dacă schimbând între ele două dintre elementele alese obții aceeași situație, folosești combinări; dacă obții alta, aranjamente.

Exemplu: $C_{5}^{3} = \frac{5 \cdot 4 \cdot 3}{3 !} = \frac{60}{6} = 10$ : un comitet de $3$ elevi dintr-un grup de $5$ se poate alege în $10$ moduri. • $C_{10}^{2} = \frac{10 \cdot 9}{2} = 45$ : atâtea meciuri are un turneu cu $10$ echipe, fiecare cu fiecare. • Numărul diagonalelor unui poligon cu $10$ laturi: $C_{10}^{2} - 10 = 45 - 10 = 35$ .

Combinări complementare — clasa 10

C_{n}^{k} = C_{n}^{n - k}, 0 \leq k \leq n

A alege $k$ elemente din $n$ înseamnă, în același timp, a alege cele $n - k$ elemente care rămân afară: o singură alegere, două citiri. De aceea indicii de sus se completează până la $n$ . Folosire practică: dacă $k > \frac{n}{2}$ , calculează combinarea complementară, care are mai puțini factori. Capcană: ecuația $C_{n}^{a} = C_{n}^{b}$ are două familii de soluții — $a = b$ sau $a + b = n$ — și amândouă trebuie scrise, apoi verificate față de condițiile $0 \leq a, b \leq n$ .

Exemplu: $C_{100}^{98} = C_{100}^{2} = \frac{100 \cdot 99}{2} = 4950$ , dintr-o singură înmulțire. • $C_{7}^{5} = C_{7}^{2} = 21$ . • Din $C_{12}^{x} = C_{12}^{5}$ rezultă $x = 5$ sau $x = 12 - 5 = 7$ .

Formula de recurență a combinărilor — clasa 10

C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}, 1 \leq k \leq n - 1

Este regula după care se construiește triunghiul lui Pascal: fiecare număr este suma celor două de deasupra lui. Demonstrația combinatorică fixează un element $x$ și împarte submulțimile cu $k$ elemente în cele care îl conțin pe $x$ (mai rămân $k - 1$ de ales dintre $n - 1$ ) și cele care nu îl conțin (toate cele $k$ se aleg dintre $n - 1$ ). Forma deplasată, $C_{n + 1}^{k + 1} = C_{n}^{k} + C_{n}^{k + 1}$ , este cea folosită la restrângeri. Capcană: formula are sens doar pentru $1 \leq k \leq n - 1$ ; la capete valorile se știu oricum, $C_{n}^{0} = C_{n}^{n} = 1$ .

Exemplu: $C_{5}^{2} = C_{4}^{1} + C_{4}^{2} = 4 + 6 = 10$ . • $C_{6}^{3} = C_{5}^{2} + C_{5}^{3} = 10 + 10 = 20$ . • Linia a patra a triunghiului lui Pascal, $1, 4, 6, 4, 1$ , se obține adunând vecinii din linia a treia, $1, 3, 3, 1$ .

Binomul lui Newton — clasa 10

(a + b)^{n} = C_{n}^{0} a^{n} + C_{n}^{1} a^{n - 1} b + \dots + C_{n}^{k} a^{n - k} b^{k} + \dots + C_{n}^{n} b^{n}

Dezvoltarea are $n + 1$ termeni: exponentul lui $a$ coboară de la $n$ la $0$ , cel al lui $b$ urcă de la $0$ la $n$ , iar în fiecare termen suma exponenților este $n$ . Coeficienții sunt exact linia $n$ din triunghiul lui Pascal. La $(a - b)^{n}$ semnele alternează, pentru că $(- b)^{k} = (- 1)^{k} b^{k}$ : termenul de rang $k + 1$ este negativ când $k$ este impar. Verificare rapidă: pentru $a = b = 1$ obții $2^{n}$ , adică suma coeficienților.

Exemplu: $(a + b)^{4} = a^{4} + 4 a^{3} b + 6 a^{2} b^{2} + 4 a b^{3} + b^{4}$ . • $(x + 2)^{3} = x^{3} + 3 x^{2} \cdot 2 + 3 x \cdot 4 + 8 = x^{3} + 6 x^{2} + 12 x + 8$ . • $(x - 1)^{4} = x^{4} - 4 x^{3} + 6 x^{2} - 4 x + 1$ , cu semnele alternând.

Termenul general al dezvoltării binomiale — clasa 10

T_{k + 1} = C_{n}^{k} a^{n - k} b^{k}, k = 0, 1, \dots, n

Formula dă orice termen al dezvoltării lui $(a + b)^{n}$ , fără să scrii toată dezvoltarea. Atenție la rang: termenul de rang $k + 1$ corespunde valorii $k$ , deci pentru termenul al patrulea iei $k = 3$ . Două verificări obligatorii: suma exponenților dintr-un termen este $n$ , iar indicele de sus al combinării este chiar exponentul lui $b$ . Pentru cerințe de tipul „termenul liber” sau „termenul care îl conține pe $x^{2}$ ”, aduni puterile lui $x$ într-un singur exponent, pui condiția și rezolvi în $k$ ; soluția trebuie să fie naturală, cu $0 \leq k \leq n$ .

Exemplu: În $(x + 2)^{6}$ , termenul care îl conține pe $x^{4}$ : din $6 - k = 4$ rezultă $k = 2$ , deci $T_{3} = C_{6}^{2} x^{4} \cdot 2^{2} = 15 \cdot 4 x^{4} = 60 x^{4}$ . • În $(x + \frac{1}{x})^{6}$ avem $T_{k + 1} = C_{6}^{k} x^{6 - 2 k}$ ; din $6 - 2 k = 0$ rezultă $k = 3$ , deci termenul liber este $C_{6}^{3} = 20$ .

Suma coeficienților binomiali — clasa 10

C_{n}^{0} + C_{n}^{1} + \dots + C_{n}^{n} = 2^{n}, C_{n}^{0} - C_{n}^{1} + \dots + (- 1)^{n} C_{n}^{n} = 0 (n \geq 1)

Prima identitate se obține punând $a = b = 1$ în binomul lui Newton, a doua punând $a = 1$ și $b = - 1$ . Prima are și o citire directă: o mulțime cu $n$ elemente are $2^{n}$ submulțimi, iar grupându-le după numărul de elemente obții tocmai combinările. A doua spune că submulțimile cu număr par de elemente sunt tot atâtea câte cele cu număr impar. Capcană: a doua identitate cere $n \geq 1$ — pentru $n = 0$ suma este $1$ .

Exemplu: $C_{4}^{0} + C_{4}^{1} + C_{4}^{2} + C_{4}^{3} + C_{4}^{4} = 1 + 4 + 6 + 4 + 1 = 16 = 2^{4}$ . • Dintr-o clasă de $10$ elevi se pot forma $2^{10} = 1024$ de echipe diferite (numărând și echipa goală, și clasa întreagă). • $C_{5}^{0} - C_{5}^{1} + C_{5}^{2} - C_{5}^{3} + C_{5}^{4} - C_{5}^{5} = 1 - 5 + 10 - 10 + 5 - 1 = 0$ .