Formule: Combinatorică

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

La liceu: ești la mate-info, la științe ale naturii sau la un liceu tehnologic? Alege profilul și listele de liceu îl arată doar pe al tău.Profilul tău la liceu (listele de liceu arată doar ce e pentru el):

Formulele tale M2 sunt primele, imediat mai jos: Pentru științe ale naturii (M2) ↓

Formulele tale de la tehnologic sunt primele, imediat mai jos: Pentru filiera tehnologică (M3) ↓

Regula produsului și regula sumei — clasa 10
Factorialul unui număr natural — clasa 10
Permutări — clasa 10
Aranjamente — clasa 10
Combinări — clasa 10
Combinări complementare — clasa 10
Formula de recurență a combinărilor — clasa 10
Binomul lui Newton — clasa 10
Termenul general al dezvoltării binomiale — clasa 10
Suma coeficienților binomiali — 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$ .

Pentru științe ale naturii (M2)

Cele 2 formule de mai jos sunt folosite de elevii de la profilul științe ale naturii (programa M2), în clasa a X-a; lecțiile lor sunt pe traseul M2 al clasei a X-a.

Principiul includerii și al excluderii M2 — clasa 10
Numărul funcțiilor de la o mulțime la alta M2 — clasa 10

Principiul includerii și al excluderii M2 — clasa 10

n (A \cup B) = n (A) + n (B) - n (A \cap B), n (A \cup B \cup C) = n (A) + n (B) + n (C) - n (A \cap B) - n (A \cap C) - n (B \cap C) + n (A \cap B \cap C)

$n (A)$ este numărul de elemente (cardinalul) al mulțimii finite $A$ . Elementele comune sunt numărate de mai multe ori la adunare, deci se scad; la trei mulțimi, intersecția tuturor ajunge la zero după cele trei scăderi, așa că se adaugă înapoi o dată — tiparul semnelor este plus, minus, plus. Un număr dat pentru „ $A$ și $B$ " înseamnă întreaga intersecție, iar elementele care nu au niciuna dintre proprietăți se numără scăzând reuniunea din numărul total de obiecte.

Exemplu: Într-o grupă de $30$ de elevi, $17$ fac chimie, $14$ fac fizică și $6$ fac amândouă: $n (A \cup B) = 17 + 14 - 6 = 25$ de elevi fac cel puțin o activitate, deci $5$ nu fac niciuna. • Câte numere din ${1, \dots, 200}$ sunt divizibile cu $4$ sau cu $6$ ? $50 + 33 - 16 = 67$ , unde intersecția înseamnă multiplii lui $cmmmc (4, 6) = 12$ , nu ai lui $24$ .

Numărul funcțiilor de la o mulțime la alta M2 — clasa 10

toate: n^{m}, injective: A_{n}^{m} = \frac{n !}{( n - m )!}, bijective: n! (numai dac \overset{a}{˘} m = n)

$m$ este numărul de elemente al domeniului $A$ , iar $n$ cel al codomeniului $B$ , pentru funcții $f : A \to B$ . Baza este numărul de valori disponibile, exponentul numărul de elemente de servit — inversarea lor schimbă complet răspunsul. Numărul funcțiilor injective este $0$ când $m > n$ , iar bijecțiile există numai dacă cele două mulțimi au același număr de elemente; tot $n!$ este și numărul de ordonări ale unei mulțimi cu $n$ elemente, fiindcă o ordonare e o bijecție de la ${1, 2, \dots, n}$ la ea.

Exemplu: Pentru $A$ cu $3$ elemente și $B$ cu $5$ : $5^{3} = 125$ funcții, dintre care $A_{5}^{3} = 5 \cdot 4 \cdot 3 = 60$ injective. • Pentru $A = B$ cu $4$ elemente: $4^{4} = 256$ funcții și $4! = 24$ bijective. • Probabilitatea ca o funcție luată la întâmplare, cu $m = 3$ și $n = 4$ , să fie injectivă: $\frac{24}{64} = \frac{3}{8}$ .

Pentru filiera tehnologică (M3)

Formula de mai jos e scrisă pentru elevii de la liceele tehnologice (programa M_tehnologic, Bacalaureatul M3), în clasa a X-a; lecțiile lor sunt pe traseul tehnologic al clasei a X-a.

Permutări, aranjamente, combinări M3 — clasa 10

Permutări, aranjamente, combinări — clasa 10

P_{n} = n! = 1 \cdot 2 \cdot \dots \cdot n, A_{n}^{k} = n (n - 1) \dots (n - k + 1) = \frac{n !}{( n - k )!}, C_{n}^{k} = \frac{A _{n}^{k}}{k !} = \frac{n !}{k ! ( n - k )!}, C_{n}^{k} = C_{n}^{n - k}

Numărul $n$ este câte obiecte distincte ai, iar $k$ , câte alegi, cu $0 \leq k \leq n$ . Primul rând, $P_{n}$ , numără ordinile tuturor obiectelor. Al doilea, $A_{n}^{k}$ , numără alegerile în care contează ordinea: un produs cu exact $k$ factori, începând de la $n$ . Al treilea, $C_{n}^{k}$ , numără alegerile fără ordine: aranjamentele se împart la $k!$ , fiindcă același grup apare în toate ordinile lui. Ultimul spune că un grup de $k$ obiecte alese îl determină pe cel de $n - k$ rămase deoparte, deci numărul lor e același. Capcană: dacă două obiecte trebuie să stea mereu alături, le lipești într-unul singur și înmulțești cu ordinile lor interne. Control: rezultatul este întotdeauna un număr întreg.

Exemplu: Un tehnician de mediu are de citit $9$ piezometre (puțuri de observație) dintr-un câmp. Le poate parcurge în $P_{9} = 9! = 362880$ de ordini. Dimineața citește patru piezometre, alese și în ordine: $A_{9}^{4} = 9 \cdot 8 \cdot 7 \cdot 6 = 3024$ de feluri. Pentru calibrarea aparatului se aleg patru piezometre, fără ordine: $C_{9}^{4} = \frac{A _{9}^{4}}{4 !} = \frac{3024}{24} = 126$ . Cele cinci rămase pentru după-amiază se aleg în $C_{9}^{5} = C_{9}^{4} = 126$ de feluri, la fel.