Deriniai

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Deriniai kombinatorikoje – baigtinės objektų aibės, turinčios n elementų, junginius iš k (1 \leq k \leq 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^{k}_{n} ir randamas pagal formulę:

C^{k}_{n} = \frac {n(n - 1)\cdot...\cdot(n - (k - 1))}{k!}, kur 1 \leq k \leq n. Pavyzdžiui: C^{5}_{8} = \frac {8\cdot7\cdot6\cdot5\cdot4}{5!}= \frac {8\cdot7\cdot6\cdot5\cdot4}{5\cdot4\cdot3\cdot2\cdot1}=56,

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

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

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

Nesunku įsitikinti, kad derinių skaičius lygus gretiniųn elementų po k elementų skaičiui padalintam iš kėlinių skaičiaus: C^{k}_{n} = \frac {A^k_n}{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^{5}_{10} = \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^{k}_{n} = C^{n-k}_{n}, kur 1 \leq k \leq n.
  • C^{k}_{n} + C^{k+1}_{n} = C^{k+1}_{n+1}

Pagal paskutiniąją derinių savybę, sudaromas Paskalio trikampis.