Gretiniai

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Sąvoka gretiniai yra vartojama kombinatorikoje.

Baigtinės objektų aibės, turinčios n elementų, junginius iš k (1 \leq k \leq n)elementų vadiname gretiniais, jeigu elementai junginyje nesikartoja ir elementų išdėstymo tvarka yra svarbi, t.y., sukeitus elementus vietomis, gaunamas naujas junginys.

Gretinių skaičius žymimas A^{k}_{n} ir randamas pagal formulę:

A^{k}_{n} = n(n - 1)\cdot...\cdot(n - (k - 1)), kur 1 \leq k \leq n.

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

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

Pavyzdžiui, kiek skirtingų trispalvių vėliavų galima pasiūti iš 5 skirtingų spalvų audeklo, galima rasti pagal gretinių formulę:

Čia n = 5, o k = 3, todėl iš viso galima pasiūti A^{3}_{5} = \frac{5!}{(5 - 3)!} = 60 skirtingų trispalvių vėliavų.

Jeigu audeklus sukeisime vietomis, tai gausime visiškai kitą vėliavą, todėl pavyzdyje aprašyti junginiai yra gretiniai.

Gretiniai, sudaryti iš visų duotosios baigtinės objektų aibės elementų, vadinami kėliniais.

[taisyti] Kartotiniai gretiniai

Junginiusm elementų, kai tuos elementus galime rinktis iš aibės, turinčios n elementų, nekreipdami dėmesio, kad elementas jau buvo pasirinktas, vadiname kartotiniais gretiniais.

Kartotinių gretinių skaičius žymimas \bar{A}^{m}_{n} ir randamas pagal formulę:

\bar{A}^{m}_{n} = n^{m}

Pavyzdžiui, kiek galima sudaryti penkiaženklių skaičių iš skaitmenų 2, 5, 9?

Akivaizdu, kad kiekvieną skaitmenį galima rinktis n = 3 būdų, todėl iš viso galima sudaryti \bar{A}^{5}_{3} = 3^{5} = 243 skaičių.