Formula de recurență a combinărilor: pe scurt

Formula de recurență: pentru $n\ge 2$ și $1\le k\le 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.

Exerciții din această mini-lecție

1. 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$.

2. 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.

3. Determinați $n\in \mathbb{N}$, $n\ge 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$ ✓.