Junginiai

Junginiai

Šiame paragrafe aptarsime pagrindinius junginius ir jø savybes.

Gretiniai be pasikartojimø

Pirmiausia aptarsime gretiniø be pasikartojanèiø elementø uždaviná.

Turime n skirtingø daiktø. Kiek iš jø galima sudaryti k-elemenèiø junginiø, sudarytø iš skirtingø elementø, kai junginys nuo junginio skiriasi arba bent vienu elementu, arba jø tvarka?

Tokie junginiai vadinami gretiniais be pasikartojimø ir žymimi simboliu .

Nesunku parodyti, kad . Šios formulës teisingumas gali bûti pagrástas taip. Sudarant k-elementá junginá, pirm¹já junginio element¹ galime pasirinkti n skirtingais bûdais; antr¹já – skirtingais bûdais, ir t.t. k-t¹já junginio element¹ galima pasirinkti skirtingais bûdais. Tada, pritaikius sandaugos dësná, gausime

Pavyzdys. Keliais skirtingais bûdais galima sudaryti trispalvê vëliav¹, turint 5 skirtingø spalvø audinius?

Kadangi vëliava nuo vëliavos skiriasi arba spalvø rinkiniu, arba jø tvarka, tai skirtingø vëliavø skaièius yra .

Gretiniai su pasikartojimais

Turime n skirtingø rûšiø daiktø. Kiek iš jø galima sudaryti k-elemenèiø junginiø, sudarytø iš skirtingø elementø, kai junginys nuo junginio skiriasi arba bent vienu elementu, arba jø tvarka ir elementai junginyje gali kartotis?

Tokie junginiai vadinami gretiniais su pasikartojanèiais elementais ir žymimi .

Sudarant toká junginá, bet kuri i-toji, , junginio pozicija gali bûti užpildyta n skirtingais bûdais. Vadinasi, .

Pavyzdys. Kiek skirtingø triženkliø skaièiø galima parašyti dešimtainëje skaièiavimo sistemoje?

Kadangi šiuo atveju , o , tai . Iš tikro, tai skaièiai 000, 001, …, 998, 999.

Këliniai be pasikartojimø

Sudarydami gretinius be pasikartojimø iš n elementø po k, gavome junginius, kurie vienas nuo kito skiriasi ir paèiais elementais, ir jø išsidëstymo tvarka.

Taèiau, jei sudarinëtume junginius iš visø n elementø, tai jie galëtø skirtis vienas nuo kito tik juose esanèiø elementø tvarka.

Tokie junginiai vadinami këliniais iš n elementø arba, trumpiau, n-elemenèiais këliniais. Juos žymësime .

Aišku, kad . Vadinasi,

Ši sandauga žymima (skaitoma: en faktorialas).

Sprendžiant praktinius uždavinius, tenka naudoti 0!. Yra susitarta, kad 0! yra lygus 1. Faktorial¹ galima nusakyti ir rekurentiškai:

Remiantis faktorialu, gretiniø formulê galima užrašyti ir taip:

Pavyzdys. Susirinkime turi kalbëti 5 žmonës. Keliais bûdais galima sudaryti kalbëtojø s¹raš¹?

Aišku, kad kalbëtojø s¹rašø skaièius yra . 

Këliniai su pasikartojanèiais elementais

Turime k skirtingø tipø daiktus. Kiek këlinø galima sudaryti iš n pirmojo tipo elementø, iš n antrojo tipo elementø, …,n_k k-tojo tipo elementø?

Kiekvien¹ këliná turi sudaryti elementø. Jei visi elementai bûtø skirtingi, tai këliniø skaièius bûtø n! Kadangi kai kurie elementai sutampa, gauname mažiau këlinø. Kad taip yra iš tikrøjø, ásitikinsime, išnagrinëjê, pavyzdžiui, këliná

kuriame iš pradžiø surašyti visi pirmojo tipo elementai, paskui – visi antrojo tipo elementai, …, pagaliau – visi k-tojo tipo elementai.

Pirmojo tipo elementus sukeitinëti vietomis galima bûdø. Kadangi tie elementai yra vienodi, tai tokie perstatinëjimai këlinio nepakeièia. Taip pat nieko nepakeièia ir antrojo tipo elementø perstatinëjimø, …, k-tojo tipo elementø perstatinëjimø.

Bet kurio tipo elementus galima sukeitinëti vien¹ su kitu nepriklausomai nuo visø kitø tipø elementø perstatinëjimo. Todël këlinio su pasikartojimais elementus sukeitinëti vien¹ su kitu vietomis taip, kad këlinys nepasikeistø, yra bûdø (taikome sandaugos dësná). Vadinasi, skirtingø këliniø su pasikartojimais skaièius lygus

Pavyzdys. Kiek këliniø galima sudaryti iš žodžio “sakalas” raidžiø?

Šiuo atveju turime dvi raides “s”, tris raides “a”, vien¹ raidê “k” ir vien¹ raidê “l”; iš viso septynias raides. Todël

Deriniai be pasikartojimø

Visi galimi k-elemenèiai junginiai iš n elementø, kai junginys nuo junginio skiriasi bent vienu elementu, vadinami deriniais ir žymimi

Deriniø skaièiaus formulê lengva sudaryti iš aukšèiau išvestos gretiniø skaièiaus formulës. Iš tikrøjø, sudarê visus k-elemenèius gretinius iš n elementø, perstatinëkime kiekvieno derinio elementus visais galimais bûdais. Taip mes sudarysime visus k-elemenèius gretinius iš n elementø; be to, kiekvienas gretinys bus gautas tik vien¹ kart¹. Vadinasi,

Tada

Pavyzdys Iš 52 kortø komplekto ištraukta 10 kortø. Keliais atvejais ištrauktøjø kortø grupëje bus bent vienas tûzas? Keliais atvejais – tik vienas tûzas? Keliais atvejais – nemažiau kaip du tûzai? Lygiai du tûzai?

Ištraukti 10 kortø yra bûdø. Skaièius atvejø, kai nëra në vieno tûzo, lygus . Todël yra atvejø, kai ištraukiamas bent vienas tûzas.

Tik vien¹ kart¹ ištraukti tûz¹ yra bûdø.

Ištraukti ne mažiau kaip du tûzus yra bûdø.

Tiksliai du tûzus galima ištraukti bûdais (du tûzus galima pasirinkti bûdais, kitas aštuonias kortas – bûdais).

Deriniai su pasikartojimais

Turime n skirtingø rûšiø daiktø. Kiek skirtingø k-elemenèiø junginiø iš n skirtingø rûšiø daiktø galima sudaryti, jei junginys nuo junginio skiriasi bent vienu elementu ir elementai junginyje gali kartotis?

Pavyzdžiui, konditerijos parduotuvëje yra 4 rûšiø pyragaièiø: eklerø, smëliniø, napoleonø ir sluoksniniø. Keliais bûdais galima nusipirkti 7 pyragaièius?

Derinius su pasikartojanèiais elementais žymësime . Apskaièiuoti deriniø su pasikartojimais skaièiø galima ávairiais bûdais. Èia aptarsime du dûdus.

Pirmasis bûdas Kiekvien¹ k-elementá deriná su pasikartojimais (kiekvien¹ 7-iø pyragaièiø rinkiná) užkoduosime taip: pirmiausia rašome tiek vienetukø, kiek pirmos rûšies daiktø yra junginyje, po to rašome 0; toliau rašome tiek vienetukø, kiek antros rûšies daiktø yra junginyje, o po jø rašome 0 ir t.t.; galiausiai rašome tiek vienetukø, kiek n-osios rûšies daiktø yra junginyje. Tuo bûdu kiekvienas kodas turës k vienetukø ir nulá. Pavyzdžiui, pyragaièiø pirkiniai 5 eklerai ir du napoleonai bei 2 eklerai, 1 smëlinis, 3 napoleonai ir 1 sluoksninis bus atitinkamai užkoduoti taip: 1111100110 ir 1101011101.

Aišku, kad kiekvienas junginys turës vienintelá kod¹ ir kiekvienas kodas atitiks skirting¹ junginá. Vadinasi,

Antrasis bûdas Tarkime, turime aibê ir k-elementá deriná su pasikartojimais , sudaryt¹ iš aibës A elementø; be to, .

Deriniui C priskirkime k-elementá deriná be pasikartojanèiø elementø, sudaryt¹ iš aibës tokiu bûdu:

Šis priskyrimas yra abipus vienareikšmis:

jei , tai ir , t.y jei , tai ir

jei yra k-elementis derinys be pasikartojimø, sudarytas iš aibës elementø, tai jam atitinkantis k-elementis derinys su pasikartojimais, sudarytas iš aibës A elementø, yra

Vadinasi,

Panagrinëkime aukšèiau pateikt¹ pavyzdá: keliais bûdais galima nusipirkti 4-iø rûšiø 7-is pyragaièius. Aišku, kad variantø skaièius yra .

Deriniø savybës

Skaièiai turi daug nuostabiø savybiø [Kn76]. Žemiau aptarsime pagrindines šiø skaièiø savybes.

. Simetriškumo savybë

Ši savybë árodoma remiantis formule:

Pritaikius ši¹ formulê skaièiui , gausime:

. Sudëties savybë

Ši¹ savybê galima árodyti dvejopai.

Pirmasis bûdas Taikykime deriniø skaièiaus formulê lygybës kairiajai ir dešiniajai pusëms. Tada , o

Iš èia išplaukia, kad lygybë yra teisinga.

Antrasis bûdas. Visus k-elemenèius derinius iš n elementø suskirstykime á dvi klases. Pirmajai klasei priklausys deriniai, kuriuose yra elementas , o antrajai – deriniai, kuriuose to elemento nëra. Jei iš bet kurio pirmosios klasës derinio išmesime element¹ , tai liks -elementis derinys, sudarytas iš elementø . Tokiø deriniø skaièius lygus . Antrosios klasës deriniai yra k-elemenèiai deriniai, sudaryti iš elementø . Todël jø skaièius lygus

Kadangi kiekvienas k-elementis derinys iš elementø priklauso vienai ir tik vienai iš tø dviejø klasiø, o visø deriniø skaièius yra , tai sumavimo savybë yra teisinga.

Sumavimo savybë yra tampriai susijusi su Paskalio trikampiu

Jei iš eilës einanèias šio trikampio eilutes sunumeruosime skaièiais , tai n-oji eilutë bus sudaryta iš skaièiø , o šios eilutës k-asis elementas , , , bus lygus , t.y. -osios eilutës nariø, esanèiø nario kairëje ir dešinëje, sumai.

Iškëlimo prieš sklaustus savybë

Jos teisingumas išplaukia iš deriniø skaièiaus formulës.

1-oji ir 3-ioji savybës ágalina rekurentiškai apskaièiuoti deriniø skaièiø .

Deriniø skaièiaus apskaièiavimo algoritmas

Duota:  n-elementø skaièius (natûralusis skaièius),

k – elementø skaièius derinyje (natûralusis skaièius).

Rasti:  .

begin

if k > n then begin C := 0; exit; end;

if k > n div 2 then k := n – k;

C

l := n – k + 1;

t

for i =1 to k do

begin

if l mod t = 0 then begin temp:=l div t; C:=C*temp; e nd

else begin temp:=C div t; C:=l*temp; e nd;

t := t+1;

l := l+1;

end

end

. Sumavimo savybës

Aptarsime dvi sumavimo savybes, kuriø teisingum¹ galima árodyti remiantis sudëties savybe:

a)   

b)  

èia n ir m – natûralieji skaièiai.

Pavyzdžiui, savybës a) teisingum¹ parodo žemiau pateikta schema, gauta nuosekliai taikant sumavimo savybê.

Savybë b) naudojama natûraliøjø skaièiø laipsniø sumoms apskaièiuoti.

Pavyzdžiui, kai , tai

Kai , galima apskaièiuoti natûraliøjø skaièiø kvadratø sum¹:

Nesunku pastebëti, kad . Vadinasi,

Kai , galima apskaièiuoti natûraliøjø skaièiø kubø sum¹. Tam tikslui išreikšime tiesiniu deriniø dariniu.

Kadangi , tai . Ávertindami, kad , o , gausime

Vadinasi,

Gautas rezultatas rodo, kad

. Binominiø koeficientø savybë

Ši¹ savybê galima árodyti remiantis garsi¹ja Niutono binomo formule:

Jei , gausime

Kitas šios formulës árodymo bûdas bûtø toks. Visus n skilèiø dvejetainius skaièius 00…0, 00…1, …, 11…1 suskirstykime á klases: k-¹j¹ klasê sudarykime iš skaièiø, kurie sudaryti iš k vienetukø ir nuliø. Aišku, kad kiekvienas skaièius priklauso tik vienai klasei, o k-osios klasës elementø skaièius yra .Kadangi skaièiø yra , tai