Deriniai

Deriniai kombinatorikoje – baigtinės objektų aibės, turinčios n elementų, junginius iš k $(1\le k\le n)$ elementų. Jeigu elementai junginyje nesikartoja ir elementų išdėstymo tvarka nėra svarbi, t. y., sukeitus elementus vietomis, gaunamas tas pats junginys.

Derinių skaičius žymimas $C_n^k$ ir randamas pagal formulę:

$C_n^k=\frac{n(n-1)(n-2)\cdot ...\cdot (n-(k-1))}{k!}=\frac{A_n^k}{P_k}=\frac{n!}{k!(n-k)!},$ kur $1\le k\le n.$

Pavyzdžiui:

$C_8^5=\frac{8\cdot 7\cdot 6\cdot 5\cdot 4}{5!}=\frac{8\cdot 7\cdot 6\cdot 5\cdot 4}{5\cdot 4\cdot 3\cdot 2\cdot 1}=56,$

Ši formulė dažniausiai taikoma kai k ir n nedideli skaičiai.

Derinių skaičių patogu rasti ir pagal kitą formulę:

$C_n^k=\frac{n!}{k!(n-k)!}$, kur n! – skaičiaus n faktorialas.

Nesunku įsitikinti, kad derinių skaičius lygus gretinių iš n elementų po k elementų skaičiui padalintam iš kėlinių skaičiaus: $C_n^k=\frac{A_n^k}{P_k}$.

Pavyzdžiui, kiek skirtingų startinių penketukų galima sudaryti iš 10 krepšininkų, galima rasti pagal derinių formulę: Čia n = 10, o k = 5, todėl iš viso galima sudaryti $C_{10}^5=\frac{10!}{5!(10-5)!}=252$ skirtingų startinių penketukų. Jeigu krepšininkus į startinį penketuką atrinksime kita tvarka, tai vis tiek gausime visiškai tą patį penketuką, todėl pavyzdyje aprašyti junginiai yra deriniai.

Deriniams teisingos lygybės:

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

Pagal paskutiniąją lygybę (dar vadinama Paskalio taisykle) yra sudaromas Paskalio trikampis, kuris naudojamas gauti dvinario $a+b$ n-tojo laipsnio koeficientus.