Formula de recurență a combinărilor

Într-o clasă de $10$ elevi trebuie aleasă o delegație de $4$ persoane pentru un concurs. Știi deja să numeri: sunt $C_{10}^4=210$ delegații posibile. Dar unul dintre elevi, Ana, are o întrebare mai fină: „Câte dintre aceste $210$ delegații mă includ pe mine?". Întrebarea ei pare să ceară un calcul nou, complicat. În realitate, ea deschide cea mai elegantă ușă din tot capitolul.

Pentru că orice delegație posibilă face parte din exact una dintre două categorii: o conține pe Ana sau nu o conține pe Ana. Nu există a treia variantă și nicio delegație nu poate fi în ambele categorii. Dacă știm să numărăm separat cele două categorii și adunăm rezultatele, obținem totalul. Iar fiecare dintre cele două numărări este mai simplă decât cea inițială, pentru că se face într-un grup cu un om mai puțin. Din această idee — banală ca gândire, puternică drept unealtă — se naște formula de recurență a combinărilor, temelia pe care se construiește triunghiul lui Pascal și, mai departe, întreaga dezvoltare a binomului lui Newton.

Ce vei învăța

• Vei ști să enunți formula de recurență a combinărilor, $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$, și să precizezi exact pentru ce valori ale lui $n$ și $k$ are sens.
• Vei ști să o demonstrezi combinatoric, prin fixarea unui element, și algebric, cu ajutorul factorialelor.
• Vei ști să o folosești „de la dreapta la stânga", ca să restrângi o sumă de două combinări alăturate într-una singură.
• Vei ști să calculezi combinări noi fără factoriale, pornind de la combinări deja cunoscute.
• Vei ști să rezolvi ecuații simple în care apar sume de combinări, de tipul $C_n^1+C_n^2=28$.
• Vei ști de ce formula aceasta este exact regula de construcție a triunghiului lui Pascal.

Hai să descoperim împreună

1. Întrebarea Anei, pe un exemplu mic

Ca să vedem clar mecanismul, micșorăm numerele. Fie mulțimea $M=\{a,b,c,d,e\}$, cu $5$ elemente, din care alegem submulțimi de câte $3$ elemente. Știm din lecția despre combinări că numărul lor este $C_5^3=10$. Le scriem pe toate:

$$\{a,b,c\},\{a,b,d\},\{a,b,e\},\{a,c,d\},\{a,c,e\},\{a,d,e\},\{b,c,d\},\{b,c,e\},\{b,d,e\},\{c,d,e\}.$$

Acum le împărțim după criteriul „conține sau nu elementul $a$":

• Cu $a$: $\{a,b,c\},\{a,b,d\},\{a,b,e\},\{a,c,d\},\{a,c,e\},\{a,d,e\}$ — sunt $6$.
• Fără $a$: $\{b,c,d\},\{b,c,e\},\{b,d,e\},\{c,d,e\}$ — sunt $4$.

Și, într-adevăr, $6+4=10$. Până aici am doar numărat. Partea interesantă este să recunoaștem ce numere sunt cele două rezultate:

• Submulțimile care îl conțin pe $a$: elementul $a$ e deja pus, mai trebuie alese încă $2$ elemente dintre cele $4$ rămase, $\{b,c,d,e\}$. Sunt $C_4^2=6$ moduri. ✓
• Submulțimile care nu îl conțin pe $a$: toate cele $3$ elemente se aleg dintre cele $4$ rămase. Sunt $C_4^3=4$ moduri. ✓

Deci $C_5^3=C_4^2+C_4^3$. Nu e o coincidență a numerelor $5$ și $3$: raționamentul nu a folosit nicăieri valorile particulare.

2. Enunțul formulei

Formula de recurență a combinărilor. Pentru orice numere naturale $n$ și $k$ cu $n\ge 2$ și $1\le k\le n-1$:

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

În cuvinte: o combinare de rang $n$ se scrie ca suma a două combinări „de deasupra ei", ambele de rang $n-1$, cu indicii superiori consecutivi $k-1$ și $k$.

Condiția $1\le k\le n-1$ nu este un moft. Dacă am lua $k=0$, în membrul drept ar apărea $C_{n-1}^{-1}$, iar combinări cu indice superior negativ pur și simplu nu există: nu poți alege $-1$ obiecte. Dacă am lua $k=n$, ar apărea $C_{n-1}^n$, adică „alegem $n$ obiecte dintr-o mulțime cu $n-1$ obiecte" — imposibil. În ambele cazuri extreme răspunsul e cunoscut oricum și fără recurență: $C_n^0=1$ și $C_n^n=1$.

3. Demonstrația combinatorică, prin fixarea unui element

Aceasta este demonstrația de reținut, pentru că explică de ce e adevărată formula, nu doar că se potrivesc calculele.

Fie $A$ o mulțime cu $n$ elemente, $n\ge 2$, și fie $k$ un număr natural cu $1\le k\le n-1$. Prin definiție, $C_n^k$ este numărul submulțimilor cu $k$ elemente ale lui $A$.

Fixăm un element oarecare al mulțimii, să-i spunem $x\in A$. Împărțim toate submulțimile cu $k$ elemente în două categorii:

Categoria I — submulțimile care îl conțin pe $x$. O astfel de submulțime este complet determinată de celelalte $k-1$ elemente ale sale, care se aleg din mulțimea $A\setminus \{x\}$, ce are $n-1$ elemente. Ordinea nu contează, deci numărul lor este $C_{n-1}^{k-1}$.

Categoria a II-a — submulțimile care nu îl conțin pe $x$. Toate cele $k$ elemente ale lor se aleg din $A\setminus \{x\}$, adică din $n-1$ elemente. Numărul lor este $C_{n-1}^k$.

Cele două categorii sunt disjuncte (o submulțime îl conține pe $x$ sau nu, nu ambele) și acoperă toate submulțimile cu $k$ elemente. Aplicând regula sumei, obținem

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

Observă cât de mult seamănă mișcarea cu pasul dintr-o demonstrație prin inducție de la metoda inducției matematice: reducem o problemă de mărime $n$ la două probleme de mărime $n-1$. Diferența e că aici reducerea nu e un artificiu de calcul, ci o descriere fidelă a realității: chiar așa arată mulțimea tuturor delegațiilor posibile, despicată în două după soarta unui singur om.

4. Demonstrația algebrică, cu factoriale

Aceeași formulă se poate obține și prin calcul, pornind de la $C_n^k=\frac{n!}{k!(n-k)!}$. Scriem cei doi termeni din membrul drept:

$$C_{n-1}^{k-1}=\frac{(n-1)!}{(k-1)!(n-k)!},C_{n-1}^k=\frac{(n-1)!}{k!(n-1-k)!}.$$

Ca să-i putem aduna, îi aducem la numitorul comun $k!(n-k)!$. Pentru primul, amplificăm cu $k$, folosind $k!=k\cdot (k-1)!$; pentru al doilea, amplificăm cu $n-k$, folosind $(n-k)!=(n-k)\cdot (n-k-1)!$:

$$C_{n-1}^{k-1}=\frac{k\cdot (n-1)!}{k!(n-k)!},C_{n-1}^k=\frac{(n-k)\cdot (n-1)!}{k!(n-k)!}.$$

Adunăm și scoatem factorul comun $(n-1)!$ de la numărător:

$$C_{n-1}^{k-1}+C_{n-1}^k=\frac{(n-1)![k+(n-k)]}{k!(n-k)!}=\frac{n\cdot (n-1)!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}=C_n^k.■$$

Toată demonstrația stă în mica minune $k+(n-k)=n$, care recompune factorialul $n!$ din $n\cdot (n-1)!$. Merită să reții tehnica amplificării cu $k$, respectiv cu $n-k$: ea reapare la aproape orice identitate cu combinări.

5. Verificări numerice și forma „deplasată" a formulei

Nu crede nicio formulă pe cuvânt; verifică-o. Iată trei verificări făcute până la capăt:

$$C_7^3=35,C_6^2+C_6^3=15+20=35.✓$$

$$C_{10}^4=210,C_9^3+C_9^4=84+126=210.✓$$

$$C_{12}^5=792,C_{11}^4+C_{11}^5=330+462=792.✓$$

În multe manuale și în multe subiecte de examen vei întâlni formula scrisă cu $n+1$ în loc de $n$. Înlocuind $n$ cu $n+1$ și $k$ cu $k+1$, obținem forma deplasată, perfect echivalentă:

$$C_{n+1}^{k+1}=C_n^k+C_n^{k+1},0\le k\le n-1.$$

Aceasta e forma cea mai comodă când citim de la dreapta la stânga, adică atunci când vrem să restrângem o sumă. De exemplu:

$$C_{15}^7+C_{15}^8=C_{16}^8=12870.$$

Regula practică de recunoaștere: se pot restrânge doar două combinări cu același indice inferior și cu indici superiori consecutivi. Rezultatul are indicele inferior mărit cu $1$ și indicele superior egal cu cel mai mare dintre cei doi.

6. Calcul fără factoriale

Formula de recurență este și o unealtă de calcul rapid. Dacă știi o „linie" de combinări, obții linia următoare doar cu adunări — fără să calculezi niciun factorial, care ar exploda oricum foarte repede ($12!=479001600$).

Pornim de la combinările lui $8$, pe care le cunoaștem: $1,8,28,56,70,56,28,8,1$. Atunci

$$C_9^4=C_8^3+C_8^4=56+70=126,C_9^5=C_8^4+C_8^5=70+56=126.$$

Și mai departe, dintr-o singură mișcare:

$$C_{10}^5=C_9^4+C_9^5=126+126=252.$$

Compară cu varianta „brutală": $C_{10}^5=\frac{10!}{5!\cdot 5!}=\frac{3628800}{120\cdot 120}$. Se poate, dar de ce, când două adunări ajung?

Recurența se combină excelent cu formula combinărilor complementare, $C_n^k=C_n^{n-k}$. De pildă:

$$C_{12}^{10}+C_{12}^{11}=C_{13}^{11}=C_{13}^2=\frac{13\cdot 12}{2}=78,$$

adică am restrâns întâi cu recurența, apoi am „întors" combinarea grea $C_{13}^{11}$ în combinarea ușoară $C_{13}^2$.

7. De aici se naște triunghiul lui Pascal

Așază combinările într-un tablou: pe linia $n$ scrii, în ordine, numerele $C_n^0,C_n^1,\dots ,C_n^n$. Prima linie (linia $0$) are un singur număr, $C_0^0=1$. Linia $1$ are $C_1^0=1$ și $C_1^1=1$. Și așa mai departe.

Formula de recurență spune atunci exact acest lucru: fiecare număr din interiorul tabloului este suma celor două numere de deasupra lui, cel din stânga-sus și cel din dreapta-sus. Capetele liniilor rămân mereu $1$, pentru că $C_n^0=C_n^n=1$.

$$\begin{array}{ccccccc}& & & 1& & & \\ & & 1& & 1& & \\ & 1& & 2& & 1& \\ 1& & 3& & 3& & 1\end{array}$$

Tabloul acesta este triunghiul lui Pascal, iar lecția următoare, Triunghiul lui Pascal, îl construiește pe zece linii și îi citește proprietățile. Ține minte doar atât: triunghiul nu e o curiozitate desenată, ci formula de recurență pusă în tabel.

8. Ecuații cu sume de combinări

Recurența transformă multe ecuații „urâte" în ecuații de gradul al doilea. Cheia e să restrângi întâi și abia apoi să calculezi. Fie ecuația

$$C_n^1+C_n^2=28,n\ge 2.$$

Restrângem membrul stâng: $C_n^1+C_n^2=C_{n+1}^2$. Deci $C_{n+1}^2=28$, adică $\frac{(n+1)n}{2}=28$, de unde $n^2+n-56=0$. Rădăcinile sunt $n_1=7$ și $n_2=-8$; a doua se respinge, pentru că $n$ este număr natural. Rămâne $n=7$, iar verificarea confirmă: $C_7^1+C_7^2=7+21=28$. ✓

Exemple rezolvate

Exemplul 1 — Verificarea directă a formulei

Verificați formula de recurență pentru $n=6$ și $k=2$.

Rezolvare. Formula afirmă că $C_6^2=C_5^1+C_5^2$. Calculăm fiecare membru separat.

Membrul stâng: $C_6^2=\frac{6\cdot 5}{2}=15$.

Membrul drept: $C_5^1=5$ și $C_5^2=\frac{5\cdot 4}{2}=10$, deci suma este $5+10=15$.

Cei doi membri coincid, $15=15$. ✓ Interpretarea concretă: dintr-un grup de $6$ persoane alegem $2$; fixând o persoană $x$, perechile care o conțin pe $x$ sunt $C_5^1=5$ (alegem partenerul), iar cele care nu o conțin sunt $C_5^2=10$.

Exemplul 2 — Urcarea pe linie, fără factoriale

Știind că $C_8^3=56$, $C_8^4=70$ și $C_8^5=56$, calculați $C_{10}^5$ folosind doar adunări.

Rezolvare. Urcăm o linie o dată:

$$C_9^4=C_8^3+C_8^4=56+70=126,C_9^5=C_8^4+C_8^5=70+56=126.$$

Apoi încă una:

$$C_{10}^5=C_9^4+C_9^5=126+126=252.$$

Deci $C_{10}^5=252$. Verificare cu formula clasică: $\frac{10!}{5!5!}=\frac{10\cdot 9\cdot 8\cdot 7\cdot 6}{120}=\frac{30240}{120}=252$. ✓

Exemplul 3 — Restrângerea unei sume

Calculați $C_{20}^{12}+C_{20}^{13}$.

Rezolvare. Cele două combinări au același indice inferior, $20$, iar indicii superiori sunt consecutivi: $12$ și $13$. Se pot deci restrânge, cu forma deplasată a recurenței:

$$C_{20}^{12}+C_{20}^{13}=C_{21}^{13}.$$

Numeric, $C_{20}^{12}=125970$ și $C_{20}^{13}=77520$, iar suma lor este $203490=C_{21}^{13}$. ✓ Reține însă că la examen nu se cere numărul, ci forma restrânsă: răspunsul așteptat este $C_{21}^{13}$.

Exemplul 4 — Delegația Anei, cu numere adevărate

Într-o clasă cu $10$ elevi se alege o delegație de $4$ persoane. Câte delegații o conțin pe Ana? Câte nu o conțin? Verificați că suma dă totalul.

Rezolvare. Totalul delegațiilor este $C_{10}^4=\frac{10\cdot 9\cdot 8\cdot 7}{24}=210$.

Delegațiile care o conțin pe Ana: Ana e deja pusă, mai alegem $3$ elevi dintre ceilalți $9$, deci $C_9^3=\frac{9\cdot 8\cdot 7}{6}=84$.

Delegațiile care nu o conțin pe Ana: toți cei $4$ se aleg dintre ceilalți $9$, deci $C_9^4=\frac{9\cdot 8\cdot 7\cdot 6}{24}=126$.

Verificare: $84+126=210=C_{10}^4$. ✓ Exact formula de recurență, îmbrăcată în povestea din deschidere.

Exemplul 5 — O ecuație cu combinări

Determinați numărul natural $n\ge 3$ pentru care $C_n^2+C_n^3=35$.

Rezolvare. Restrângem membrul stâng cu recurența: $C_n^2+C_n^3=C_{n+1}^3$. Ecuația devine

$$C_{n+1}^3=35,\text{adica˘}\frac{(n+1)n(n-1)}{6}=35,$$

deci $(n+1)n(n-1)=210$. Căutăm trei numere naturale consecutive cu produsul $210$: încercăm $5\cdot 6\cdot 7=210$. ✓ Deci $n-1=5$, $n=6$, $n+1=7$.

Verificare în ecuația inițială: $C_6^2+C_6^3=15+20=35$. ✓ Soluția este $n=6$.

Exemplul 6 — Exemplu tip Bacalaureat

Se consideră numărul natural $n\ge 3$. a) Demonstrați că $C_n^2+C_n^3=\frac{n(n^2-1)}{6}$. b) Calculați $C_{10}^2+C_{10}^3$.

Rezolvare. a) Aplicăm formula de recurență în forma deplasată, cu indicii superiori consecutivi $2$ și $3$:

$$C_n^2+C_n^3=C_{n+1}^3=\frac{(n+1)!}{3!(n-2)!}=\frac{(n+1)n(n-1)}{6}.$$

Recunoaștem la numărător produsul $n\cdot (n-1)(n+1)=n(n^2-1)$, deci

$$C_n^2+C_n^3=\frac{n(n^2-1)}{6}.$$

b) Pentru $n=10$: $\frac{10\cdot (100-1)}{6}=\frac{10\cdot 99}{6}=\frac{990}{6}=165$.

Verificare directă: $C_{10}^2=45$, $C_{10}^3=120$, iar $45+120=165$. ✓ (Este chiar $C_{11}^3=165$.)

Să exersăm

Rezolvă pe caiet. La combinări, baremul punctează scrierea formulei folosite, nu doar numărul final — scrie de fiecare dată ce recurență aplici și pentru ce valori ale lui $n$ și $k$.

1. Calculează $C_6^2+C_6^3$ folosind formula de recurență, apoi verifică rezultatul prin calcul direct.

2. Scrie $C_9^5$ ca sumă de două combinări de rang $8$ și calculează.

3. Verifică prin calcul direct egalitatea $C_7^2=C_6^1+C_6^2$.

4. Completează pătrățelul: $C_{11}^4=C_{10}^{\square }+C_{10}^4$. Justifică alegerea.

5. Știind că $C_9^2=36$ și $C_9^3=84$, calculează $C_{10}^3$ fără să folosești factoriale.

6. (Adevărat/Fals cu motivare.) „Formula $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$ se poate aplica și pentru $k=0$."

7. Restrânge într-o singură combinare: $C_{15}^7+C_{15}^8$.

8. Restrânge într-o singură combinare: $C_{20}^{12}+C_{20}^{13}$.

9. Demonstrează, folosind recurența, că $C_n^1+C_n^2=C_{n+1}^2$ pentru orice $n\ge 2$, și verifică egalitatea pentru $n=5$.

10. Determină numărul natural $n\ge 2$ pentru care $C_n^1+C_n^2=28$.

11. (Problemă aplicată.) Într-un club cu $12$ membri se formează un comitet de $5$ persoane. Câte comitete îl conțin pe Radu și câte nu îl conțin? Verifică faptul că suma celor două numere dă totalul comitetelor posibile.

12. Calculează $C_8^3+C_8^4+C_9^5$, restrângând pas cu pas.

13. (Adevărat/Fals cu motivare.) „$C_{10}^4+C_{10}^5=C_{11}^5$."

14. Folosind întâi recurența și apoi combinările complementare, calculează $C_{12}^{10}+C_{12}^{11}$.

15. Explică, prin fixarea unui element, de ce numărul submulțimilor cu $4$ elemente ale mulțimii $\{1,2,\dots ,9\}$ care îl conțin pe $1$ este $C_8^3$, iar al celor care nu îl conțin este $C_8^4$.

16. (Exercițiu tip Bacalaureat.) a) Demonstrați că $C_n^{k-1}+2C_n^k+C_n^{k+1}=C_{n+2}^{k+1}$, pentru $1\le k\le n-1$. b) Verificați egalitatea pentru $n=6$ și $k=2$.

17. Într-un grup de $n$ persoane ($n\ge 4$), dintre care una este Maria, se aleg $3$ persoane. Scrie, folosind combinări, numărul grupelor care o conțin pe Maria și numărul celor care nu o conțin, apoi arată că suma lor este $C_n^3$.

18. (Provocare.) Aplicând repetat formula de recurență, demonstrează identitatea $C_2^2+C_3^2+C_4^2+\cdots +C_n^2=C_{n+1}^3$, pentru orice $n\ge 2$. Verifică apoi pentru $n=5$.

Răspunsuri și explicații

1. $C_6^2+C_6^3=C_7^3=35$. Verificare directă: $C_6^2=15$, $C_6^3=20$, iar $15+20=35$; pe de altă parte $C_7^3=\frac{7\cdot 6\cdot 5}{6}=35$. ✓

2. $C_9^5=C_8^4+C_8^5=70+56=126$. (Se putea și $C_9^5=C_9^4=126$, prin combinări complementare.)

3. $C_7^2=\frac{7\cdot 6}{2}=21$; $C_6^1=6$, $C_6^2=15$, iar $6+15=21$. ✓

4. Pătrățelul este $3$: $C_{11}^4=C_{10}^3+C_{10}^4$. Indicii superiori din membrul drept trebuie să fie consecutivi, $k-1=3$ și $k=4$. Numeric: $120+210=330=C_{11}^4$. ✓

5. $C_{10}^3=C_9^2+C_9^3=36+84=120$.

6. Fals. Pentru $k=0$ în membrul drept ar apărea $C_{n-1}^{-1}$, care nu este definită — nu se pot alege $-1$ obiecte. Formula are sens doar pentru $1\le k\le n-1$. De altfel, pentru $k=0$ răspunsul e cunoscut oricum: $C_n^0=1$.

7. $C_{15}^7+C_{15}^8=C_{16}^8$ (indice inferior comun $15$, indici superiori consecutivi). Numeric, $6435+6435=12870$. ✓

8. $C_{20}^{12}+C_{20}^{13}=C_{21}^{13}$. Numeric, $125970+77520=203490$. ✓

9. Cu forma deplasată a recurenței, pentru $k=1$: $C_n^1+C_n^2=C_{n+1}^2$. Pentru $n=5$: $C_5^1+C_5^2=5+10=15$, iar $C_6^2=\frac{6\cdot 5}{2}=15$. ✓

10. Restrângem: $C_{n+1}^2=28$, deci $\frac{(n+1)n}{2}=28$, adică $n^2+n-56=0$, cu rădăcinile $7$ și $-8$. Cum $n\in \mathbb{N}$, rămâne $n=7$. Verificare: $7+21=28$. ✓

11. Total: $C_{12}^5=792$. Cu Radu: fixăm Radu și alegem $4$ dintre ceilalți $11$, deci $C_{11}^4=330$. Fără Radu: alegem toți cei $5$ dintre ceilalți $11$, deci $C_{11}^5=462$. Verificare: $330+462=792$. ✓

12. Întâi $C_8^3+C_8^4=C_9^4=126$; apoi $C_9^4+C_9^5=C_{10}^5=252$. Deci rezultatul este $252$. (Numeric: $56+70+126=252$.) ✓

13. Adevărat. Indicele inferior este comun ($10$), indicii superiori sunt consecutivi ($4$ și $5$), deci suma este $C_{11}^5$. Numeric: $210+252=462=C_{11}^5$. ✓

14. $C_{12}^{10}+C_{12}^{11}=C_{13}^{11}$, iar prin combinări complementare $C_{13}^{11}=C_{13}^2=\frac{13\cdot 12}{2}=78$. Verificare: $66+12=78$. ✓

15. Submulțimile care îl conțin pe $1$: elementul $1$ e deja ales, restul de $3$ elemente se iau din $\{2,3,\dots ,9\}$, mulțime cu $8$ elemente, deci sunt $C_8^3=56$. Cele care nu îl conțin pe $1$: toate cele $4$ elemente se iau din aceeași mulțime cu $8$ elemente, deci sunt $C_8^4=70$. Total: $56+70=126=C_9^4$. ✓

16. a) Grupăm termenii ca $(C_n^{k-1}+C_n^k)+(C_n^k+C_n^{k+1})=C_{n+1}^k+C_{n+1}^{k+1}=C_{n+2}^{k+1}$, aplicând recurența de trei ori. b) Pentru $n=6$, $k=2$: $C_6^1+2C_6^2+C_6^3=6+30+20=56$, iar $C_8^3=56$. ✓

17. Grupele care o conțin pe Maria: $C_{n-1}^2$ (mai alegem $2$ dintre ceilalți $n-1$). Grupele care nu o conțin: $C_{n-1}^3$. Suma lor este $C_{n-1}^2+C_{n-1}^3=C_n^3$, exact formula de recurență pentru $k=3$.

18. Pentru $m\ge 3$, recurența $C_{m+1}^3=C_m^2+C_m^3$ se rescrie ca $C_m^2=C_{m+1}^3-C_m^3$. Aplicând-o termenilor de la $C_3^2$ încolo, suma devine telescopică:

$$C_3^2+C_4^2+\cdots +C_n^2=(C_4^3-C_3^3)+(C_5^3-C_4^3)+\cdots +(C_{n+1}^3-C_n^3)=C_{n+1}^3-C_3^3.$$

Mai adăugăm primul termen al sumei inițiale, $C_2^2=1=C_3^3$, și obținem exact $C_{n+1}^3$. Verificare pentru $n=5$: $1+3+6+10=20$, iar $C_6^3=20$. ✓

De reținut

• Formula de recurență a combinărilor: $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$, valabilă pentru $n\ge 2$ și $1\le k\le n-1$. În afara acestui interval nu are sens, iar valorile de la capete se știu oricum: $C_n^0=C_n^n=1$.
• Demonstrația combinatorică se face prin fixarea unui element $x$: submulțimile cu $k$ elemente se împart în cele care îl conțin pe $x$ (sunt $C_{n-1}^{k-1}$) și cele care nu îl conțin (sunt $C_{n-1}^k$); regula sumei încheie demonstrația.
• Forma deplasată, $C_{n+1}^{k+1}=C_n^k+C_n^{k+1}$, e cea folosită la restrângeri: două combinări cu același indice inferior și cu indici superiori consecutivi se adună într-una singură.
• Recurența îți permite să calculezi combinări numai cu adunări, fără factoriale — de aceea e regula de construcție a triunghiului lui Pascal.
• La ecuații de tipul $C_n^1+C_n^2=28$, restrângi întâi și abia apoi calculezi; obții o ecuație de gradul al doilea, din care păstrezi doar soluțiile naturale acceptabile.

Greșeli frecvente

• Aplicarea formulei pentru $k=0$ sau $k=n$. Ar apărea $C_{n-1}^{-1}$ sau $C_{n-1}^n$, adică simboluri fără sens. Reține condiția $1\le k\le n-1$ și rezolvă cazurile extreme direct: $C_n^0=C_n^n=1$.
• Restrângerea unor combinări care nu se pot restrânge. $C_{10}^3+C_{10}^5$ nu este $C_{11}^5$: indicii superiori trebuie să fie consecutivi. La fel, $C_9^4+C_{10}^5$ nu se restrânge — indicii inferiori diferă.
• Confuzia dintre indicele de sus și cel de jos. În $C_n^k$, $n$ este numărul total de obiecte, iar $k$ numărul celor alese. La restrângere, indicele inferior crește cu $1$, iar cel superior devine cel mai mare dintre cei doi, nu suma lor.
• Uitarea verificării la ecuații. După ce rezolvi $n^2+n-56=0$ și găsești $n_1=7$, $n_2=-8$, trebuie să respingi explicit valoarea negativă și să verifici că soluția păstrată respectă condiția de existență (aici $n\ge 2$).
• „Demonstrația" prin verificarea unui singur caz. Faptul că $C_5^3=C_4^2+C_4^3$ nu demonstrează formula pentru orice $n$ și $k$ — e doar o verificare. Demonstrația este raționamentul cu fixarea unui element sau calculul cu factoriale.

Aplică acasă

1. Delegația din familia ta. Scrie pe o hârtie numele a $5$ persoane apropiate și listează toate grupele de câte $3$ care se pot forma (sunt $C_5^3=10$). Apoi taie-le cu markerul pe cele care te conțin pe tine: trebuie să fie exact $C_4^2=6$. Numărul rămas, $4$, este $C_4^3$. Ai reprodus, cu mâna ta, demonstrația din lecție.

2. Linia următoare, doar cu adunări. Scrie pe o linie numerele $1,6,15,20,15,6,1$ (combinările lui $6$) și obține linia următoare adunând vecinii doi câte doi, punând $1$ la capete. Verifică cu calculatorul că numerele obținute sunt într-adevăr $C_7^0,C_7^1,\dots ,C_7^7$.

3. Meniul de la cantină. Dacă la cantină sunt $8$ feluri de mâncare și îți alegi $3$, câte meniuri conțin felul tău preferat și câte nu? Calculează cele două numere ($C_7^2$ și $C_7^3$), adună-le și compară cu $C_8^3$. Apoi întreabă un coleg cu ce fel preferat ar face el calculul — răspunsul e același, ceea ce arată că nu contează care element fixăm.

Pentru părinți și profesori

Lecția introduce prima identitate combinatorică demonstrată din programa clasei a X-a și este, ca metodă, pasul cel mai important al capitolului: elevul trece de la „aplic o formulă" la „justific o formulă printr-un raționament de numărare". Ideea de a fixa un element și de a împărți cazurile în două categorii disjuncte este cea care se va relua, aproape identic, la triunghiul lui Pascal, la binomul lui Newton și, în clasele următoare, în probabilități.

Ce verifică lecția: (1) enunțul corect al formulei, cu condițiile de valabilitate $1\le k\le n-1$; (2) demonstrația combinatorică, redactată în două categorii disjuncte; (3) demonstrația algebrică, cu amplificarea corectă la numitor comun; (4) restrângerea sumelor, cu recunoașterea tiparului „același indice inferior, indici superiori consecutivi"; (5) rezolvarea unei ecuații simple prin restrângere. Întrebări bune de control: „De ce nu putem lua $k=0$?", „Ce înseamnă concret $C_{n-1}^{k-1}$ în problema cu delegația?", „Se poate restrânge $C_9^3+C_9^5$?" (nu, indicii superiori nu sunt consecutivi).

Semne că elevul a înțeles: explică formula cu propriile cuvinte, pe o poveste („fie îl iau pe Radu în echipă, fie nu"), și nu are nevoie de factoriale ca să calculeze o combinare nouă dintr-o linie cunoscută. La Bacalaureat, formula apare la subiectul I și la subiectul al II-lea, în general sub forma restrângerii unei sume sau a rezolvării unei ecuații de tipul $C_n^2+C_n^3=a$; ea este și pasul-cheie în problemele care cer justificarea unei identități cu coeficienți binomiali.

Întrebări frecvente

Care este formula de recurență a combinărilor? Este egalitatea $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$, valabilă pentru numere naturale cu $n\ge 2$ și $1\le k\le n-1$. Ea spune că o combinare se obține adunând două combinări de rang cu $1$ mai mic, cu indicii superiori consecutivi.

Cum se demonstrează formula de recurență a combinărilor? Cel mai frumos, combinatoric: fixezi un element $x$ al mulțimii și împarți submulțimile cu $k$ elemente în cele care îl conțin pe $x$ (mai alegi $k-1$ elemente din $n-1$, deci $C_{n-1}^{k-1}$) și cele care nu îl conțin ($C_{n-1}^k$). Categoriile sunt disjuncte, deci numerele se adună. Există și o demonstrație algebrică, prin aducerea celor două fracții cu factoriale la același numitor.

De ce nu se poate aplica formula pentru $k=0$? Pentru că în membrul drept ar apărea $C_{n-1}^{-1}$, care nu are sens: nu poți alege un număr negativ de obiecte. La fel, pentru $k=n$ ar apărea $C_{n-1}^n$, adică alegerea a $n$ obiecte dintr-o mulțime cu $n-1$ obiecte. Cazurile acestea se rezolvă direct: $C_n^0=C_n^n=1$.

Când pot restrânge o sumă de două combinări? Doar când cele două combinări au același indice inferior și indicii superiori consecutivi. Atunci $C_n^k+C_n^{k+1}=C_{n+1}^{k+1}$: indicele inferior crește cu $1$, iar cel superior este cel mai mare dintre cei doi. Sumele de tipul $C_{10}^3+C_{10}^5$ nu se pot restrânge.

Ce legătură are formula de recurență cu triunghiul lui Pascal? Este chiar regula lui de construcție. Dacă scrii pe linia $n$ numerele $C_n^0,C_n^1,\dots ,C_n^n$, formula spune că fiecare număr din interior este suma celor două numere de deasupra sa. Capetele rămân $1$, pentru că $C_n^0=C_n^n=1$.

Cum calculez o combinare fără factoriale? Pornești de la o linie cunoscută a triunghiului lui Pascal și aduni vecinii. De exemplu, din $C_8^4=70$ și $C_8^5=56$ obții imediat $C_9^5=126$. E mult mai rapid decât să calculezi $9!$, $5!$ și $4!$, mai ales la numere mari.

Cum rezolv o ecuație de tipul $C_n^1+C_n^2=28$? Restrângi întâi membrul stâng cu recurența: $C_n^1+C_n^2=C_{n+1}^2$. Obții $\frac{(n+1)n}{2}=28$, adică o ecuație de gradul al doilea, $n^2+n-56=0$, cu soluțiile $7$ și $-8$. Păstrezi doar soluția naturală, $n=7$, și o verifici în ecuația inițială.

Unde apare formula de recurență la Bacalaureat? La subiectul I, în exerciții scurte de restrângere sau de calcul ($C_9^3+C_9^4=?$), și la subiectele următoare, în probleme care cer determinarea unui număr natural dintr-o ecuație cu combinări sau justificarea unei identități. Este și pasul obligatoriu în orice raționament care folosește triunghiul lui Pascal.