Care egalitate este formula de recurență a combinărilor?

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

$$C_n^k = C_{n-1}^{k-1} \cdot C_{n-1}^{k}$$

$$C_n^k = C_n^{k-1} + C_n^{k}$$

Cum restrâng suma Cₙ^(k-1)+2Cₙ^(k)+Cₙ^(k+1)?

Aplici recurența de două ori, pe perechi de termeni vecini, apoi încă o dată pe cele două rezultate: Cₙ^(k-1)+Cₙ^(k)=Cₙ₊₁^(k) și Cₙ^(k)+Cₙ^(k+1)=Cₙ₊₁^(k+1), apoi Cₙ₊₁^(k)+Cₙ₊₁^(k+1)=Cₙ₊₂^(k+1). Verificare pentru n=5 și k=2: suma este 5+20+10=35, iar C₇³=35.

Pentru ce n are loc Cₙ⁴+Cₙ⁵=C₁₀⁵?

Restrângi membrul stâng: Cₙ⁴+Cₙ⁵=Cₙ₊₁⁵. Ecuația devine Cₙ₊₁⁵=C₁₀⁵. Pentru un indice de sus fixat, Cₘ⁵ crește odată cu m, deci două valori egale cer același m: n+1=10 și n=9.

Câte loturi conțin o anumită probă?

Profilul tău de liceu: nu l-ai ales încăProfilul tău: mate-info (M1)Profilul tău: științe ale naturii (M2); pagina asta e pentru științe ale naturii (M2) — mini-lecția M1 pereche → ·

Lecția pe scurt · clasa a X-a · Recurența combinărilor

Dacă proba $P$ trebuie să fie în lot, mai alegi $k - 1$ probe din celelalte $n - 1$ : $C_{n - 1}^{k - 1}$ loturi. Loturile fără $P$ sunt $C_{n - 1}^{k}$ , iar împreună dau toate loturile, de unde formula de recurență. Exemplu: din $12$ probe, loturi de câte $4$ . Cu $P$ sunt $C_{11}^{3} = 165$ , fără $P$ sunt $C_{11}^{4} = 330$ , iar $165 + 330 = 495 = C_{12}^{4}$ .

Fixează un element al unei colecții cu $n$ obiecte și privește toate alegerile de $k$ obiecte. Unele îl conțin pe elementul fixat: pentru ele mai trebuie alese $k - 1$ obiecte dintre celelalte $n - 1$ . Altele nu îl conțin: toate cele $k$ obiecte vin dintre cele $n - 1$ rămase. Cazurile se exclud și acoperă totul, deci se adună: $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$ , pentru $n \geq 2$ și $1 \leq k \leq n - 1$ .

Citită invers, formula strânge într-una singură o sumă de combinări vecine de pe același rând: $C_{n}^{k} + C_{n}^{k + 1} = C_{n + 1}^{k + 1}$ . Cunoscând două valori vecine, afli valoarea aflată dedesubt adunându-le, iar factorialele nu mai sunt necesare; o foaie de calcul construiește așa tabele întregi. Mutând un termen, apare regula diferențelor: $C_{n + 1}^{k} - C_{n}^{k} = C_{n}^{k - 1}$ .

În ecuații restrângi întâi suma, apoi cauți numere consecutive în jurul rădăcinii potrivite a produsului. Când membrul drept e o combinare dată, nu uita de forma ei complementară.

De reținut

$C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$ : cu elementul fixat plus fără el
$C_{n}^{k} + C_{n}^{k + 1} = C_{n + 1}^{k + 1}$
$C_{n + 1}^{k} - C_{n}^{k} = C_{n}^{k - 1}$

Greșeala tipică

Pentru loturile care conțin proba $P$ se scrie $C_{n}^{k - 1}$ , lăsând proba printre cele de ales; ea e deja în lot, deci se aleg $k - 1$ probe din $n - 1$ .

Exerciții din această mini-lecție

Care egalitate este formula de recurență a combinărilor?
- a) $C_{n}^{k} = C_{n - 1}^{k} + C_{n - 1}^{k + 1}$
- b) $C_{n}^{k} = C_{n - 1}^{k - 1} \cdot C_{n - 1}^{k}$
- c) $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$
- d) $C_{n}^{k} = C_{n}^{k - 1} + C_{n}^{k}$
Vezi răspunsul

Răspuns corect: c) $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$

Alegerile care conțin un element fixat sunt $C_{n - 1}^{k - 1}$ , cele care nu îl conțin sunt $C_{n - 1}^{k}$ , iar cele două cazuri se adună.
Suma $C_{86}^{20} + C_{86}^{21}$ este egală cu:
- a) $C_{87}^{20}$
- b) $C_{86}^{41}$
- c) $C_{172}^{41}$
- d) $C_{87}^{21}$
Vezi răspunsul

Răspuns corect: d) $C_{87}^{21}$

Același $n$ , indici de sus consecutivi: rezultatul are $n + 1 = 87$ și indicele de sus mai mare, $21$ .
Dintr-un set de $40$ de probe se formează loturi de câte $5$ . Ce parte dintre toate loturile posibile conține o probă anume, fixată dinainte?
- a) $\frac{1}{40}$
- b) $\frac{1}{8}$
- c) $\frac{1}{5}$
- d) $\frac{5}{39}$
Vezi răspunsul

Răspuns corect: b) $\frac{1}{8}$

Loturile cu proba fixată sunt $C_{39}^{4}$ , iar toate loturile sunt $C_{40}^{5} = \frac{40}{5} \cdot C_{39}^{4}$ . Raportul lor este $\frac{5}{40} = \frac{1}{8}$ , adică numărul probelor dintr-un lot împărțit la numărul tuturor probelor.

Întrebări conexe

Ce fracție din toate loturile conțin o probă fixată?

Raportul este $\frac{C _{n - 1}^{k - 1}}{C _{n}^{k}} = \frac{k}{n}$ . Pentru $12$ probe și loturi de $4$ : $\frac{165}{495} = \frac{1}{3} = \frac{4}{12}$ . Fiecare lot are $4$ locuri din $12$ probe, deci o probă dată apare în o treime din loturi.

Cum calculez $C_{11}^{5}$ doar prin adunări?

Aplici recurența pe linia de deasupra: $C_{11}^{5} = C_{10}^{4} + C_{10}^{5} = 210 + 252 = 462$ . Dacă nu știi valorile liniei $10$ , le obții la fel din linia $9$ , fără factoriale, cum face o foaie de calcul.

Cât este $C_{15}^{3} - C_{14}^{3}$ ?

Regula diferențelor dă $C_{15}^{3} - C_{14}^{3} = C_{14}^{2} = 91$ . Explicația: diferența numără exact grupele de câte $3$ care conțin elementul al cincisprezecelea, adăugat mulțimii cu $14$ elemente. Verificare directă: $C_{15}^{3} = 455$ și $C_{14}^{3} = 364$ , iar $455 - 364 = 91$ .

Cum restrâng suma $C_{n}^{k - 1} + 2 C_{n}^{k} + C_{n}^{k + 1}$ ?

Aplici recurența de două ori, pe perechi de termeni vecini, apoi încă o dată pe cele două rezultate: $C_{n}^{k - 1} + C_{n}^{k} = C_{n + 1}^{k}$ și $C_{n}^{k} + C_{n}^{k + 1} = C_{n + 1}^{k + 1}$ , apoi $C_{n + 1}^{k} + C_{n + 1}^{k + 1} = C_{n + 2}^{k + 1}$ . Verificare pentru $n = 5$ și $k = 2$ : suma este $5 + 20 + 10 = 35$ , iar $C_{7}^{3} = 35$ .

Pentru ce $n$ are loc $C_{n}^{4} + C_{n}^{5} = C_{10}^{5}$ ?

Restrângi membrul stâng: $C_{n}^{4} + C_{n}^{5} = C_{n + 1}^{5}$ . Ecuația devine $C_{n + 1}^{5} = C_{10}^{5}$ . Pentru un indice de sus fixat, $C_{m}^{5}$ crește odată cu $m$ , deci două valori egale cer același $m$ : $n + 1 = 10$ și $n = 9$ .

Oamenii mai întreabă și: loturi care conțin o probă fixată · câte grupe conțin un element anume · combinări cu un element obligatoriu · numărul submulțimilor care conțin un element dat

Câte loturi conțin o anumită probă?

De reținut

Greșeala tipică

Exerciții din această mini-lecție

Întrebări conexe

Ce fracție din toate loturile conțin o probă fixată?

Cum calculez C115​ doar prin adunări?

Cât este C153​−C143​?

Cum restrâng suma Cnk−1​+2Cnk​+Cnk+1​?

Pentru ce n are loc Cn4​+Cn5​=C105​?

Continuă cu

Cum calculez $C_{11}^{5}$ doar prin adunări?

Cât este $C_{15}^{3} - C_{14}^{3}$ ?

Cum restrâng suma $C_{n}^{k - 1} + 2 C_{n}^{k} + C_{n}^{k + 1}$ ?

Pentru ce $n$ are loc $C_{n}^{4} + C_{n}^{5} = C_{10}^{5}$ ?