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