Cum adun două combinări vecine?

Lecția pe scurt · clasa a X-a · Formula de recurență a combinărilor

Dacă au același număr de sus și indicii de jos sunt consecutivi, suma lor este o singură combinare: $C_{n}^{k - 1} + C_{n}^{k} = C_{n + 1}^{k}$ . Explicația este simplă: fixezi un element și separi submulțimile care îl conțin de cele care nu îl conțin. De pildă, $C_{18}^{9} + C_{18}^{10} = C_{19}^{10}$ . Regula cere ambele condiții; dacă indicii de sus diferă sau cei de jos nu sunt vecini, restrângerea nu se poate face.

Formula de recurență: pentru $n \geq 2$ și $1 \leq k \leq n - 1$ , $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k} .$ Demonstrația combinatorică fixează un element $x$ al mulțimii: submulțimile cu $k$ elemente care îl conțin pe $x$ sunt determinate de restul de $k - 1$ elemente, alese dintre celelalte $n - 1$ — sunt $C_{n - 1}^{k - 1}$ ; cele care nu îl conțin aleg toate cele $k$ elemente dintre cele $n - 1$ rămase — sunt $C_{n - 1}^{k}$ . Cele două categorii se exclud și acoperă tot, deci se adună.

Forma deplasată, $C_{n + 1}^{k + 1} = C_{n}^{k} + C_{n}^{k + 1}$ , e cea folosită pentru restrângere: două combinări cu același indice inferior și indici superiori consecutivi se adună într-una singură, cu indicele inferior mărit cu $1$ și cel superior egal cu cel mai mare dintre cei doi. Regula nu funcționează dacă indicii superiori nu sunt consecutivi sau indicii inferiori diferă.

Recurența e chiar regula de construcție a triunghiului lui Pascal: fiecare număr e suma celor două de deasupra lui. La ecuații de tipul $C_{n}^{1} + C_{n}^{2} = S$ , restrângi întâi ( $= C_{n + 1}^{2}$ ) și abia apoi rezolvi.

De reținut

$C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$
forma pentru restrângere: $C_{n}^{k} + C_{n}^{k + 1} = C_{n + 1}^{k + 1}$
condiții: $n \geq 2$ și $1 \leq k \leq n - 1$

Greșeala tipică

Se adună două combinări cu indicii de jos depărtați, ca $C_{n}^{1} + C_{n}^{3}$ , ca și cum ar fi vecine. Restrângerea cere indici consecutivi; altfel suma se calculează termen cu termen.

Exerciții din această mini-lecție

Verificați formula de recurență: $C_{9}^{4}$ este egal cu:
- a) $C_{8}^{3} + C_{8}^{4} = 56 + 70 = 126$
- b) $C_{8}^{3} \cdot C_{8}^{4}$
- c) $C_{8}^{4} - C_{8}^{3}$
- d) $C_{8}^{3} + C_{8}^{3} = 112$
Vezi răspunsul

Răspuns corect: a) $C_{8}^{3} + C_{8}^{4} = 56 + 70 = 126$

Fixând un element, submulțimile cu $4$ elemente care îl conțin sunt $C_{8}^{3} = 56$ , iar cele care nu îl conțin sunt $C_{8}^{4} = 70$ . Suma: $56 + 70 = 126 = C_{9}^{4}$ .
Ce combinare rezultă din restrângerea sumei $C_{18}^{9} + C_{18}^{10}$ ?
- a) $C_{19}^{9}$
- b) $C_{19}^{10}$
- c) $C_{18}^{19}$
- d) $C_{36}^{19}$
Vezi răspunsul

Răspuns corect: b) $C_{19}^{10}$

Indicii inferiori sunt egali ( $18$ ), iar cei superiori sunt consecutivi ( $9, 10$ ): rezultatul este $C_{19}^{10}$ — indicele inferior crește cu $1$ , cel superior devine cel mai mare dintre cei doi.
Determinați $n \in N$ , $n \geq 2$ , pentru care $C_{n}^{1} + C_{n}^{2} = 66$ .
- a) $n = 12$
- b) $n = 10$
- c) $n = 11$
- d) $n = - 12$
Vezi răspunsul

Răspuns corect: c) $n = 11$

Restrângem: $C_{n}^{1} + C_{n}^{2} = C_{n + 1}^{2} = \frac{n ( n + 1 )}{2}$ . Ecuația $\frac{n ( n + 1 )}{2} = 66$ dă $n (n + 1) = 132$ ; testăm $n = 11$ : $11 \cdot 12 = 132$ ✓.

Întrebări conexe

Ce se întâmplă dacă indicii de sus nu sunt consecutivi?

Suma nu se poate strânge într-o singură combinare. Relația fixează un element și desparte submulțimile în două categorii, ceea ce cere exact indici vecini. Pentru $C_{n}^{1} + C_{n}^{3}$ , de pildă, calculezi fiecare termen separat și abia apoi aduni valorile obținute.

Cu ce este egală suma C de 18 luate câte 9, plus C de 18 luate câte 10?

Numerele de sus coincid, iar cele de jos sunt vecine, deci restrângerea se poate face: rezultatul este $C_{19}^{10}$ . Numărul de sus a crescut cu unu, iar cel de jos a rămas cel mai mare dintre $9$ și $10$ .

Ce valoare are n dacă C de n luate câte 1, plus C de n luate câte 2, este 66?

Restrângi suma într-o singură combinare: $C_{n}^{1} + C_{n}^{2} = C_{n + 1}^{2} = \frac{n ( n + 1 )}{2}$ , deci $n (n + 1) = 132$ . Cauți două numere naturale consecutive cu acest produs și găsești $11 \cdot 12 = 132$ , așadar $n = 11$ . Verificarea directă confirmă: $11 + 55 = 66$ , exact cât cere enunțul.

Cum verific formula de recurență pe C de 9 luate câte 4?

Fixezi un element din mulțimea cu nouă elemente. Submulțimile de patru care îl conțin se completează cu trei dintre celelalte opt, deci sunt $C_{8}^{3} = 56$ ; cele care nu îl conțin sunt $C_{8}^{4} = 70$ . Suma este $126$ , exact cât face $C_{9}^{4}$ .

De ce se citește formula de recurență pe triunghiul lui Pascal?

Pentru că fiecare număr din triunghi este suma celor două de deasupra lui, iar asta este chiar relația dintre o combinare și cele două de pe rândul dinainte. Așa poți completa un rând întreg fără să calculezi nicio factorială, folosind numai adunări.

Ce valoare are n dacă C de n luate câte 2, plus C de n luate câte 3, este 56?

Restrângi suma la $C_{n + 1}^{3} = \frac{( n + 1 ) n ( n - 1 )}{6}$ , deci produsul celor trei numere consecutive trebuie să fie $336$ . Cauți trei numere vecine cu acest produs și găsești $6 \cdot 7 \cdot 8 = 336$ , de unde $n = 7$ . Verificarea directă confirmă: $21 + 35 = 56$ , exact valoarea din enunț.

Oamenii mai întreabă și: formula de recurență a combinărilor · suma a două combinări vecine · restrângerea unei sume de combinări · triunghiul lui Pascal formula · C de n luate câte k egal suma a două combinări