Formula de recurență a combinărilor

Formulă din tema Combinatorică, clasa a X-a — cu legenda literelor și un exemplu rezolvat.

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

Formula de recurență a combinărilor

Continuă cu