Kombinatorikos įvadas

3. Kombinatorika 3.1. Įvadas Ne taip paprasta pateikti išsamų kombinatorikos apibrėžimą. Kažkuria prasme žodį “kombinatorika” galima suprasti kaip “diskrečiosios matematikos” sinonimą, t.y. mokslą, tyrinėjantį diskrečiasias baigtines matematines struktūras. Šia prasme žodis “kombinatorika” atsispindi žymaus lenkų matematiko Vytoldo Lipskio knygos “Witold Lipski. Kombinatorika dla programistow. Wydawnictva Naukowo – Techniczne. Warszava, 1982” (yra vertimas į rusų kalbą žr. [Lip88]) pavadinime. Paprastai kombinatorika suprantama kaip matematikos sritis, kurioje tiriami klausimai, kiek skirtingų kombinacijų, tenkinančių vienokias ar kitokias sąlygas, galima sudaryti iš turimų objektų. Kombinatorika atsirado 16 amžiuje ir buvo susijusi su azartiniais lošimais. Buvo tiriama, keliais būdais galima išmesti kokį nors akių skaičių, lošiant dviem ar trim kauliukais, arba keliais būdais galima gauti, pavyzdžiui, du karalius, lošiant kortomis. 17 amžiuje prancūzų matematikai Paskalis ir Ferma nagrinėjo statytos sumos padalijimo uždavinį. Problema buvo tokia: lošimas turėjo vykti iki t išloštų partijų, bet buvo nutrauktas, kai vienam žaidėjui iki išlošimo lieka r partijų, o antrajam – s partijų. Kaip žaidėjai turi pasidalyti statytąją sumą? Tolesnė kombinatorikos raida susijusi su Jakobo Bernulio, Leibnico ir Oilerio vardais. Pastaraisiais metai kombinatorikos vystymasis glaudžiai siejasi su optimizavimo uždavinų sprendimu, šifravimo ir dekodavimo uždavinias bei kitomis informacijos teorijos problemomis. 3.2. Bendrieji kombinatorikos dėsniai Sprendžiant įvairius kombinatorikos uždavinius, dažniausiai naudojami sumavimo, sandaugos, priskirties ir išskirties dėsniai. Sumavimo dėsnis Jei kokiam nors objektui A pasirinkti yra m būdų, o kitam objektui B pasirinkti yra n būdų, tai pasirinkti “arba A, arba B” yra m + n būdų. Pastaba. Taikant taip suformuluotą sumavimo dėsnį, reikia žiūrėti, kad nei vienas objekto A pasirinkimo būdas nesutaptų su kuriuo nors objekto B pasirinkimo būdu. Jei tokių sutapimų yra k, tai susidaro m + n – k pasirinkimo būdų. Pavyzdys. Pintinėje yra 12 obuolių ir 10 apelsinų. Jonukas pasirenka arba obuolį, arba apelsiną, o paskui Onutė ima ir obuolį, ir apelsiną. Keliais būdais Jonukas gali paimti vaisių ir kada Onutei didesnė pasirinkimo laisvė: ar kai Jonukas paima obuolį, ar kai apelsiną? Aišku, kad Jonukas obuolį gali pasirinkti 12 skirtingų būdų, o apelsiną – 10 skirtingų būdų. Vadinasi, pasirinkti arba obuolį, arba apelsiną galima 12 + 10 = 22 būdais. Į antrą klausimo dalį atsakysime po sandaugos dėsnio. Sandaugos dėsnis Jei objektui A pasirinkti yra m būdų, o po kiekvieno tokio pasirinkimo objektą B galima pasirinkti n būdais, tai porą (A, B) pasirinkti nurodytąja tvarka galima m  n būdais. Pavyzdys. Panagrinėkime aukščiau pateiktą pavyzdį. Tarkime, Jonukas pasirinko obuolį. Tada Onutei galimų pasirinkimo būdų yra 11  10. Jei Jonukas būtų pasirinkęs apelsiną, tai Onutei paimti ir obuolį, ir apelsiną būtų galima 12  9 būdais. Kadangi 11  10 > 12  9, tai Onutei didesnė pasirinkimo laisvė bus tada, jei Jonukas pasirinks obuolį. Priskirties ir išskirties dėsnis Sakykime, kad kai kuriems iš N turimų daiktų būdingos savybės . Simboliu pažymėkime skaičių daiktų, turinčių savybes (į kitas tų daiktų savybes nekreipiame dėmesio). Jei reikės pabrėžti, kad imami tik tie daiktai, kurie neturi kurios nors savybės, tai tą savybę rašysime su brūkšneliu. Pavyzdžiui, žymi skaičių daiktų, turinčių savybes ir , bet neturinčių savybės (į kitas jų savybes nekreipiame dėmesio). Tada priskirties ir išskirties dėsnis bus užrašomas taip: (3.2.1) Įrodymas. Šį dėsnį įrodysime pilnosios matematinės indukcijos metodu. Dėsnis teisingas, kai kiekvienas daiktas turi savybę . Tada . Tarkime, kad dėsnis teisingas, kai savybių skaičius lygus : (3.2.2) Įrodysime, kad dėsnis teisingas, kai savybių skaičius yra n. (3.2.2) formulę taikykime daiktų aibei. Gausime: (3.2.3) Iš (3.2.2) lygybės atėmę (3.2.3), gausime (3.2.4) (3.2.4) formulės kairiosios pusės skirtumas yra lygus , nes iš skaičiaus daiktų, kurie neturi savybių atimame skaičių daiktų, neturinčių tų pačių savybių ir turinčių savybę . Vadinasi, atėmus liks skaičus daiktų, neturinčių savybių . Pavyzdys. Pasinaudodami priskirties ir išskirties formule, apskaičuokime, kiek tarp natūraliųjų skaičių nuo vieneto iki 100 yra skaičių, kurie nesidalo nei iš 2-jų, nei iš 3-jų, nei iš penkių. Tarkime, – tai skaičiaus savybė dalintis iš 2-jų, – tai skaičiaus savybė dalintis iš 3-jų, o – tai skaičiaus savybė dalintis iš 5-ių. Tada Norint sužinoti, kiek skaičių nuo 1 iki N dalijasi iš n, reikia N padalinti iš n ir imti gautojo dalmens sveikąją dalį į mažesniąją pusę. Todėl , , , , , , . Vadinasi, . 3.3. Junginiai Šiame paragrafe aptarsime pagrindinius junginius ir jų savybes. 3.3.1. 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 . 3.3.2. 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. 3.3.3. 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 . 3.3.4. Kėliniai su pasikartojančiais elementais Turime k skirtingų tipų daiktus. Kiek kėlinų galima sudaryti iš n1 pirmojo tipo elementų, iš n2 antrojo tipo elementų, …,nk 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 . 3.3.5. 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). 3.3.6. 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: 1) jei , tai ir , t.y jei , tai ir ; 2) 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 . 3.3.7. Derinių savybės Skaičiai turi daug nuostabių savybių [Kn76]. Žemiau aptarsime pagrindines šių skaičių savybes. 1. Simetriškumo savybė . Ši savybė įrodoma remiantis formule: Pritaikius šią formulę skaičiui , gausime: . 2. 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. 3. 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 := 1; l := n – k + 1; t := 1; 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; 4. 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 . 5. 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 . 3.4. Kombinatorinių objektų generavimo algoritmai Šiame paragrafe aptarsime pagrindinius kombinatorinių objektų (derinių, kėlinių, aibės išskaidymo ir kt.) generavimo algoritmus. Optimali tokių objektų generavimo algoritmo struktūra yra: begin generuoti pradinį junginį (kombinatorinį objektą); while “generavimo sąlyga” do begin nagrinėti (spausdinti) junginį (kombinatorinį objektą); generuoti junginį (kombinatorinį objektą), gretimą išnagrinėtam (atspausdintam). end; end; Priklausomai nuo pasirinktų objektų bei jų generavimo tvarkos, šiame algoritme turi būti konkretizuoti sakiniai “generuoti pradinį junginį”, “generavimo sąlyga”, “generuoti gretimą junginį”. 3.4.1. Derinių generavimo algoritmai Derinių generavimas leksikografine tvarka Pirmiausia aptersime derinių generavimo leksikografine didėjimo tvarka algoritmą. Apie leksikografinę vektorių tvarką kalbėjome 1.3 paragrafe. Čia priminsime, kad jei į derinį žiūrėsime kaip į skaičių, tai deriniams atitinkantys skaičiai bus išdėstyti didėjimo tvarka. Pavyzdys. Panagrinėkime . Deriniai, surašyti leksikografine tvarka, bus: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345. Derinius nuosekliai talpinsime masyve ir šio masyvo elementai apibrėš derinį. Pradinio derinio generavimas. Aišku, kad pradinis derinys generuojamas taip: for l := 0 to k do c [l] := l; Kaip generuoti patį mažiausią leksikografiškai didesnį derinį nei turimas? Tarkime, – turimas derinys. Leksikografine tvarka pats didžiausias derinys yra: . Vadinasi, , . todėl, norint apskaičiuoti patį mažiausią leksikografiškai didesnį derinį nei nagrinėjamas derinys, elgsimės taip: 1) masyve rasime pirmą iš dešinės elementą cl, , tenkinantį sąlygą ; 2) šį elementą padidinsime vienetu, t.y. ; 3) likusius elementus užpildysime iš eilės einančiais natūraliaisiais skaičiais, t.y. for i := l + 1 to k do ci: = ci-1 + 1; Generavimo pabaigos sąlyga. Jei pirmasis iš dešinės elementas, tenkinantis sąlygą , yra , tai reiškia, kad nagrinėjame derinį: . Vadinasi, jau visi deriniai sugeneruoti. Tuo būdu, derinių generavimo leksikografine tvarka algoritmas yra. Derinių skaičiaus apskaičiavimo algoritmas Duota: n – objektų skaičius, k – objektų skaičius derinyje. Rasti: generuoti derinius leksikografine tvarka. begin { c [0..k] – masyvas, kurio elementai nusako derinį } for l := 0 to k do c [l] := l; { Pradinio derinio generavimas } p := true; { Generavimo sąlyga } while p do begin spausdinti derinį ; { Generuoti leksikografiškai didesnį derinį } l := k; while (l >= 1) and c [l] >= n – k + l do l := l – 1; if l = 0 then p := false else begin c [l] := c [l] + 1; for i := l + 1 to k do c [i] := c [i – 1] + 1; end; end; { while p } end; Trečiasis Grėjaus kodų generavimo algoritmas Kaip matyti iš antrojo Grėjaus kodo generavimo algoritmo (žr. 1.3 paragrafą), Grėjaus kodus galima generuoti iš pradinio kodo, žinant seką . Šios sekos elementas žymi skiltį, kurią reikia invertuoti, kad iš -ojo kodo gautume i-ąjį kodą. Pavyzdžiui, kai , seka T3 yra tokia: . Vadinasi, pakanka mokėti efektyviai generuoti seką Tn, kad galėtume generuoti Grėjaus kodus. Seką Tn galima efektyviai generuoti naudojant steką. Pradžioje stekas užpildomas elementais: (viršuje yra elementas 1). Algoritmas ima viršutinį steko elementą i ir patalpina jį į seką Tn; po to į steką įrašomi elementai . Būtent tokiu būdu žemiau pateiktas algoritmas generuoja Grėjaus kodus. begin s := 0; { s – tuščias stekas } for j := n downto 1 do begin g [j] := 0; s  j; end; while s   do begin spausdinti ; i  s; g [i] := 1 – g [i]; for j := i – 1 downto 1 do s  j; end; { while } end; end; Skaičiuojant pagal šį algoritmą, steko turinys (viršutinis elementas yra steko viršūnėje) kis taip: , o i reikšmės sudarys T3 seką . Pateiktą algoritmą galima patobulinti. Kiekvieną kartą, kai į steką patalpinamas elementas , mes apriori žinome, kad virš jo bus patalpinti elementai . Protingas šios informacijos panaudojimas įgalina vietoj steko naudoti masyvą tokiu būdu. Elementas yra viršutinis steko elementas ir kiekvienam yra elementas, steke esantis tuoj po elemento j (žemiau elemento j), jei j yra steke. Jei elemento j steke nėra, tai elemento reikšmė negali turėti jokios įtakos skaičiavimams ir todėl priskiriame reikšmę , kadangi mes žinome, kad kai kitą kartą elementas bus patalpintas į steką, elementu, esančiu virš jo, bus elementas j. Dar daugiau, kadangi elementai bus talpinami į steką pašalinus elementą i, mums reikia tiktai priskirti , laikant, kad visiems j, , reikšmė buvo priskirta, kai j buvo pašalintas iš steko (primename, tada ). Pagaliau, kai , elementai į steką patalpinami operacijos dėka. Dabar gausime tokį algoritmą. begin for j := 0 to n + 1 do begin g [j] := 0;  [j] := j + 1; end; i := 0; while i 1 gi = 1, t > 0 gi = 0, t = 1 gi = 1, t = 0 Šie pertvarkymai turi įtakos vienetukų skaičiui tarp skilčių : t reikšmę turime sumažinti 1, jei , ir padidinti 1, jei . Pereinant prie gretimo kodo yra invertuojamos dvi skiltys: 1) skiltis , ir 2) , , , . Atlikus šiuos veiksmus, į steką reikia įrašyti papildomą informaciją: tarpines viršūnes, esančias tarp nagrinėjamos viršūnės ir nagrinėjamos kabančios viršūnės. Kadangi tas priklauso nuo viršūnės steko viršuje, tai t reikšmė gali vėl pasikeisti. Jei arba , tai reiškia, kad viršūnė, kurioje mes esame, yra kabanti viršūnė: arba ir jokių tarpinių viršūnių saugoti nereikia. Šiuo atveju t visada lygus . Kita vertus, jei ir , tai į steką turime įtraukti viršūnes , išskyrus tą atvejį, kai . Šiuo atveju į steką įtraukiame tik . Parametro t reikšmė turi būti perskaičiuojama. Kadangi tarp vienetukų gali būti tik , tai . Be to, jei šiuo atveju t tampa lygus 0, tai . Žemiau pateiktas derinių generavimo minimalaus pokyčio tvarka algoritmas. Šiame algoritme stekas organizuojamas masyvu , o jo viršutinis elementas yra (žr. trečiąjį Grėjaus kodų generavimo algoritmą). Kadangi , tai ekvivalentu, kad į steką įtraukiame . const nn = 20; type mas = array [0..nn] of integer; var n, i, k : integer; g, tau : mas; procedure der (n, k : integer); var i, j, t : integer; g, tau : mas; begin for j := 1 to k do begin g [j] := 1; tau [j] := j + 1; end; for j := k + 1 to n + 1 do begin g [j] := 0; tau [j] := j + 1; end; t := k; tau [1] := k + 1; i := 0; while i n + 1 do begin writeln; for j := n downto 1 do write (g [j] : 3); writeln; i := tau [1]; tau [1] := tau [i]; tau [i] := i + 1; if g [i] = 1 then begin if t 0 then g[t]:=1-g[t] else g[i-1]:=1-g[i-1]; t:=t+1; end else begin if t 1 then g [t – 1] := 1 – g [t – 1] else g [i – 1] := 1 – g [i – 1]; t := t – 1; end; g [i] :=1 – g [i]; if (t = i – 1) or (t = 0) then t := t + 1 else begin t := t – g [i – 1]; tau [i – 1] := tau [1]; if t = 0 then tau [1] := i – 1 else tau [1]:=t+1; end; end; end; begin writeln ('įveskite n'); readln (n); writeln ('įveskite k'); readln (k); der (n, k); end. Atsitiktinio derinio generavimas Aptarsime atsitiktinio poaibio, turinčio k elementų, iš aibės, turinčios n elementų , generavimą. Aišku, kad tokio poaibio generavimo tikimybė yra . Tam tikslui atsitiktinai parenkame vieną iš n elementų (pasirinkimo tikimybė ) ir po to atsitiktinai generuojame -elementį poaibį iš likusių elementų. Tada šios procedūros eigoje k-elemenčio poaibio išsirinkimo tikimybė yra tokių tikimybių sandauga: P (pirmasis išsirinktas elementas – vienas iš k elementų ) , P (antrasis išsirinktas elementas – vienas iš k – 1 likusių elementų) , _ _ _ __ _ _ __ _ _ __ _ _ __ _ _ __ _ _ _ P (k-asis išsirinktas elementas – paskutinysis iš likusių elementų) . Ši sandauga bus lygi: . Aptarsime atsitiktinio derinio generavimo algoritmą. Algoritmo realizavimui panaudosime papildomą masyvą p, kuriame saugosime dar neišrinktų elementų numerius. Po to, kai pirmieji elementai išsirinkti, tai bus sąrašas elementų, kurie dar neišsirinkti. Kadangi nebūtina išsaugoti elementų tvarką, tai, išsirinkus elementą , , įjo vietą įrašome neišsirinktą elementą . Žemiau pateikiamas atsitiktinio derinio generavimo algoritmas. begin for j := 1 to n do p [j] := j; R := ; for j := 1 to k do begin r := rand (j, n); { rand (j, n) – tolygiai pasiskirsčiusių atsitiktinių skaičių iš intervalo [j, n] generavimo procedūra } R := R  {a [p [r]]}; p [r] := p [j]; end; end; 3.4.2. Kėlinių generavimo algoritmai Kėlinių generavimo leksikografine tvarka algoritmas Aptarsime kėlinių iš n elementų generavimo leksikografine tvarka uždavinį. Spręsdami šį uždavinį, laikysime aukščiau pateiktos (žr. 3.4 paragrafo pradžią) kombinatorinų objektų generavimo algoritmo struktūros. Norėdami išsiaiškinti šio algoritmo pagrindinius momentus, panagrinėkime pavyzdį, kai . Pradinio kodo generavimas. Kėlinį talpinsime masyve , kurio elementai ir nusako kėlinį. Aišku, kad pradinis kėlinys yra . Pavyzdžiu, jei , tai . Paties mažiausio, leksikografiškai didesnio kėlinio nei nagrinėjamas, apskaičiavimas. Tarkime, – nagrinėjamas kėlinys. Pavyzdžiui, . Jei į kėlinį žiūrėsime kaip į skaičių, tai reikia rasti patį mažiausią skaičių, didesnį nei nagrinėjamas. Tam tikslui reikia: 1) rasti pirmą iš dešinės porą tokią, kad , 2) rasti , t.y tarp elementų rasti patį mažiausią elementą, didesnį už , 3) elementus ir sukeisti vietomis, 4) elementus (“uodegą”) surašyti atvirkščia tvarka (“apversti”). Pavyzdžiui, pirmoji iš dešinės pora, tenkinanti 1) punkto reikalavimą, yra , o elementas . Tada, sukeitę 4 su 5, gausime . “Apvertę uodegą”, gausime patį mažiausią leksikografiškai didesnį kėlinį nei duotas: . Generavimo pabaigos sąlyga. Aišku, kad pats didžiausias kėlinys yra (masyvo elementas yra pagalbinis, ir jo reikšmė lygi nuliui). Tada pirma iš dešinės pora , tenkinanti sąlygą yra . Kitaip tariant, jei , tai generavimo pabaiga. Vadinasi, kėlinių generavimo leksikografine tvarka algoritmas gali būti užrašytas taip. begin fo i:= 0 to n do p [i] :=i; t := true; while t do begin spausdinti ; { Leksikografiškai didesnio kėlinio apskaičiavimas } i := n – 1; while p [i] > p [i+ 1] do i := i – 1; if i = 0 then t := false else begin { Rasti } j := n; while p [j] p [i] do i := i + 1; if i = n + 1 then t := false else begin { Rasti } j := 1; while p [j] > p [i] do j := j + 1; { Elementus pi ir pj sukeisti vietomis } pp := p [i]; p [i] := p [j]; p [j] := pp; { Elementus surašyti atvirkščia tvarka } k := 1; l := i - 1; while k m do begin d [m] := – d [m]; m := m – 1; end; if m = 1 then t := false else begin { Sukeisti p [a [m]] su p [a [m] + d [m]] } pp := p [a [m]]; p [a [m]] := p [a [m] + d [m]]; p [a [m] + d [m]] : =pp; { Sukeisti elementų m ir p [a [m] + d [m]] adresus. Po sukeitimo elementas p [a [m] + d [m]] yra p [a [m]] vietoje. Vadinasi, keisime a [m] ir a [p [a [m]]] } pp := a [m]; k := p [a [m]]; a [m] := a [k]; a [k] : =pp; end; end; { while } end; Kai , pateiktas algoritmas apskaičiuoja: 1234 1243 1423 4123 4132 1432 1342 1324 3124 3142 3412 4312 4321 3421 3241 3214 2314 2341 2431 4231 4213 2413 2143 2134 Atsitiktinio kėlinio generavimas Tarkime, kad – bet koks kėlinys. Perskaičiuokime šį kėlinį pagal algoritmą: begin for i := n downto 2 do sukeisti p [i] su p [rand (1, i)], čia rand [k, l] – tolygiai pasiskirsčiusių atsitiktinių skaičių iš atkarpos [k, l] generavimo procedūra; end; Taip gautas kėlinys p su tikimybe gali sutapti su bet kuriuo kėliniu iš visų kėlinių aibės. Tam, kad įrodytume, jog visi kėliniai vienodai galimi, pasinaudokime matematinės indukcijos metodu. Kai – akivaizdu. Tarkime, kad algoritmas generuoja atsitiktinį kėlinį, kai elementų skaičius yra . Tegu yra bet kuris aibės kėlinys. Tada tikimybė, kad yra: 3.4.3. Aibės išskaidymas n-elementės aibės X išskaidymas į k poaibių (blokų) – tai aibės X poaibių šeima , kurios elementai tenkina reikalavimus: 1) , 2) , 3) . Poaibius vadinsime blokais. Aibės X visų galimų išskaidymų į k blokus aibę žymėsime , o aibės X visų galimų išskaidymų aibę žymėsime . Aišku, kad . Su aibės X išskaidymu į blokus yra susiję Stirlingo ir Belo skaičiai. Antrosios rūšies Stirlingo skaičius – tai skirtingų n-elementės aibės išskaidymo į k blokus skaičius, t.y. čia . Pavyzdžiui, , kadangi yra 7 skirtingi 4-ių elementų aibės išskaidymo į du blokus būdai: , , , , , , . Akivaizdu, kad , kai . Be to, , kadangi tuščia blokų aibė sutinkamai su apibrėžimu yra tuščiosios aibės išskaidymas. Su antrosios rūšies Stirlingo skaičiais, kaip ir su binominiais koeficientais, yra susiję daug tapatybių. Pirmiausia įrodysime tapatybę, primenančią derinių sudėties savybę, kuri yra susijusi su Paskalio trikampiu: a) , , b) , , (3.4.2) c) , . Formulių ir teisingumas akivaizdus. 3.4.1 a) formulės teisingumą įrodysime taip. Visus n-elementės aibės išskaidymus į k blokų suskirstykime į dvi klases. Pirmajai klasei priskirkime visus išskaidymus, kuriuse yra vienelementinis blokas , o antrajai klasei priskirkime visus išskaidymus, kai elementas n yra didesnio bloko (mažiausiai dviejų elementų aibės) elementas. Aišku, kad pirmosios klasės galia yra , t.y. tokia, kokia yra aibės išskaidymo į blokus galia. Antrosios klasės galia yra , kadangi prie kiekvieno išskaidymo į k blokus k skirtingais būdais galima prijungti elementą n: elementas n paeiliui jungiamas prie kiekvieno bloko. (1.3.4) formulė įgalina lengvai apskaičiuoti . Žemiau pateikta reikšmių lentelė, primenanti Paskalio trikampį. Šią lentelę galima traktuoti kaip “Stirlingo trikampį”. i-osios eilutės elementas yra lygus -osios eilutės elemento iš kairės ir -osios eilutės elemento iš viršaus, padauginto iš k, sumai. 6 lentelė. Antrosios rūšies Stirlingo skaičiai n\ k 0 1 2 3 4 5 6 7 8 9 10 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 2 0 1 1 0 0 0 0 0 0 0 0 3 0 1 3 1 0 0 0 0 0 0 0 4 0 1 7 6 1 0 0 0 0 0 0 5 0 1 15 25 10 1 0 0 0 0 0 6 0 1 31 90 65 15 1 0 0 0 0 7 0 1 63 301 350 140 21 1 0 0 0 8 0 1 127 966 1701 1050 266 28 1 0 0 9 0 1 255 3025 7770 6951 2646 462 36 1 0 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 Antrosios rūšies Stirlingo skaičiai yra susiję su n- osios eilės polinomo , užrašyto bazėje , užrašymu bazėje , čia . Teorema [Lip88]. Kiekvienam . Pavyzdžiui, . Iš tikro, Pirmosios rūšies Stirlingo skaičiai. Šie skaičiai žymimi ir jie yra koeficientai prie x laipsnių daugianaryje , t.y. . Kitaip tariant, skaičiai vaidina atvirkščią vaidmenį atžvilgiu , t.y. leidžia polinomą, užrašytą bazėje pervesti į polinomo užrašą bazėje . Nesunku parodyti (palyginant koeficientus prie laipsnių lygybėje ), kad tenkina sąryšius: , , , , (3.4.3) , . . Žemiau pateikta pirmosios rūšies Stirlingo skaičių lentelė. 7 lentelė. Pirmosios rūšies Stirlingo skaičiai n\ k 0 1 2 3 4 5 6 7 8 9 10 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 2 0 -1 1 0 0 0 0 0 0 0 0 3 0 2 -3 1 0 0 0 0 0 0 0 4 0 -6 11 -6 1 0 0 0 0 0 0 5 0 24 -50 35 -10 1 0 0 0 0 0 6 0 -120 274 -225 85 -15 1 0 0 0 0 7 0 720 -1764 1624 -735 175 -21 1 0 0 0 8 0 -5040 13068 -13132 6769 -1960 322 -28 1 0 0 9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1 0 10 0 -362880 1026576 -1172700 723680 -269325 63273 -9450 870 -45 1 Belo skaičius Bn. Belo skaičius – tai visų galimų n-elementės aibės X išskaidymo į blokus skaičius: , čia . Kitaip tariant, . Įrodysime Belo skaičius siejantį rekurentinį sąryšį: , . (3.4.4) Aibės visų galimų išskaidymų aibę galima išskaidyti į klases, priklausomai nuo bloko B, turinčio savyje elementą , arba, kas ekvivalentu, priklausomai nuo aibės . Kiekvienai aibei egzistuoja tiksliai aibės X išskaidymų, turinčių savyje bloką B. Grupuodami klases priklausomai nuo aibės galios, gauname (3.4.3) formulę. Žemiau pateikta Belo skaičių lentelė. 8 lentelė. Belo skaičiai n Bn 0 1 1 1 2 2 3 5 4 15 5 52 6 203 7 877 8 4 140 9 21 147 10 115 975 11 678 570 12 4 213 597 13 27 644 437 14 190 899 322 15 1 382 958 545 Aibės išskaidymo generavimo algoritmas Aptarsime n-elementės aibės visų galimų išskaidymų generavimo algoritmą. Šio algoritmo idėją lengviausia paaiškinti suformulavus ją rekurentinėje formoje. Aišku, kad kiekvienas aibės išskaidymas  vienareikšmiškai nusako aibės išskaidymą n-1, gautą iš išskaidymo , kai iš jo atitinkamo bloko pašalinamas elementas n (ir pašalinamas tuščiasis blokas, jei elementas n sudarė vienelementį bloką). Ir atvirkščiai, jei turime aibės išskaidymą , tai lengva rasti visus aibės išskaidymus , kad , t.y. (3.4.5) Ši savybė įgalina sudaryti paprastą rekurentinį metodą, generuojantį visus galimus aibės išskaidymus: jei mes žinome aibės visų galimų išskaidymų sąrašą Ln-1, tai visų galimų aibės išskaidymų sąrašas Ln gaunamas pakeičiant kiekvieną sąrašo Ln-1 išskaidymą  (3.4.5) seka. Be to, nesunku pastebėti, jei kas antram sąrašo sąrašo Ln-1 išskaidymui  invertuosime (rašysime atvirkščia tvarka) (3.4.5) seką, tai sąrašo Ln gretimi išskaidymai mažai skirsis vienas nuo kito. Tiksliau kalbant, kiekvienas gretimas sąrašo Ln išskaidymas bus gautas iš prieš jį esančio išskaidymo pašalinant kažkokį elementą iš kažkurio bloko ir patalpinant šį elementą į kitą bloką, arba sukuriant iš jo vienelementinį bloką. Pavyzdžiui, jei , tai gausime tokius sąrašus: . Toliau aptarsime nerekurentinę šio metodo realizaciją. Aibės išskaidymo blokus surašysime jų mažiausio elemento didėjimo tvarka. Bloko mažiausią elementą mes vadinsime bloko numeriu. Reikia pažymėti, kad gretimų blokų numeriai bendru atveju nėra iš eilės einą natūralieji skaičiai. Šiame algoritme naudosime kintamuosius ir , , atitinkamai reiškiančius prieš ir po bloko, kurio numeris i, stovinčių blokų numerius. Jei blokas, kurio numeris i, yra paskutinysis išskaidymo blokas, tai . Naudosime kintamąjį , . Jei , tai reiškia, kad i-tasis aibės elementas priklauso blokui, kurio numeris k. Elemento judėjimo kryptį nusakys kintamasis , . Jei , tai elementas i “juda” pirmyn. Žemiau pateiktas algoritmas generuoja visus galimus aibės išskaidymo būdus, kai duotas aibės elementų skaičius n. Algoritmo rezultatas: visų galimų aibės išskaidymų seka, kurioje kiekvienas išskaidymas gaunamas iš prieš tai buvusio, perkeliant vienintelį elementą į kitą bloką. begin for i := 1 to n do { Elementą i patalpinti į pirmąjį bloką } begin blok [i] := 1; pirmyn [i] := true; end; sek [1] := 0; Atspausdinti išskaidymą: elementai, masyve blok pažymėti tuo pačiu numeriu k, priklauso k-ajam blokui. j := n; { j = aktyvusis elementas } while j > 1 do begin k := blok [j]; if pirmyn [j] then { j “juda” į priekį } begin if sek [k] := 0 then { k yra paskutinysis blokas } begin sek [k] := j; prec [j] := k; sek [j] := 0; end; if sek [k] > j {j sudaro naują bloką } begin prec [j] := k; sek [j] := sek [k]; prec [sek [j]] := j; sek [k] := j; end; blok [j] := sek [k] end else {j “juda” atgal } begin blok [j] := prec [k]; if k = j then { j sudaro vienelementį bloką } if sek [k] = 0 then sek [prec [k]] := 0; else begin sek [prec [k]] := sek [k]; prec [sek [k]] := prec [k]; end; end; Atspausdinti išskaidymą. j := n; while ((j > 1) and ((pirmyn [j]) and (blok [j] = j)) or ((not pirmyn [j]) and (blok [j] := 1))) do begin pirmyn [j] := not pirmyn [j]; j := j – 1; end; end; end; Pateiktas algoritmas pradžioje generuoja išskaidymą , t.y. pirmąjį aibės išskaidymą sąraše Ln, kuris gaunamas aukščiau aprašytu rekurentiniu metodu. Pagrindinio ciklo “while j > 1 do” paskirtis yra “aktyvaus” elemento j radimas ir jo perkėlimas į kaimyninį bloką, t.y. į bloką iš dešinės, jei pirmyn [j] turi reikšmę true (šiuo atveju gali būti sukuriamas blokas {j}), ir į bloką iš kairės, jei pirmyn [j] = false. Iš aukščiau pateikto rekurentinio metodo išplaukia, kad elementas j gali būti “judinamas”, kai visi didesni už jį elementai pasiekia savo ribinę kairiąją arba dešiniąją padėtį. Kitaip tariant, “aktyvusis elementas” j* yra toks elementas, kai visi didesni už jį elementai j (j > j*) tenkina vieną iš dviejų sąlygų: a) pirmyn [j] and (blok [j] = j), t.y. elementas juda pirmyn (į dešinę) ir pasiekia savo dešiniąją ribinę padėtį (aišku, kad j negali būti elementu bloko, kurio mažiausias elementas yra didesnis už j); b) not pirmyn [j] and (blok [j] = 1), t.y. elementas juda atgal (į kairę) ir pasiekia savo kairiąją ribinę padėtį. Aišku, kad, jei elementas j tenkina vieną iš minėtų sąlygų, tai keičiama jo judėjimo kryptis. Paanalizuokime “aktyvaus” elemento perkėlimo į kitą bloką procesą. Pirmiausia randamas numeris bloko, kuriame yra aktyvusis elementas. Tarkime, kad tokio bloko numeris yra k. Jei “aktyvusis” elementas “juda” į dešinę, tai pakanka perkelti jį į bloką, kurio numeris yra , jei ir . Jei arba , tai pirmiausia reikia modifikuoti reikšmę. Tarkime, sek [k] = 0. Vadinasi, “aktyviojo” elemento blokas yra paskutinysis išskaidymo blokas. Šiuo atveju bus sudaromas naujas blokas {j}. Tam tikslui pakanka priimti: ir atitinkamai pakeisti ir reikšmes (žr. algoritmo tekstą). Tarkime, sek [k] > j. Tai reiškia, kad visi blokai, esantys dešiniau bloko k, sudaryti iš elementų, didesnių nei j (visi tie elementai užima ribinę dešinę padėtį). Vadinasi, (žr. rekurentinį metodą), šiuo atveju reikia sukurti vienelementį bloką {j}. Tai ir įvykdoma (žr. algoritmo tekstą). Situacijoje, kai “aktyvusis” elementas juda atgal (į kairę), pakanka patalpinti šį elementą į prieš bloką k stovintį bloką ir atlikti atitinkamus masyvų sek ir prec elementų pakeitimus. Žemiau surašyti visi galimi aibės išskaidymo būdai, apskaičiuoti pagal aukščiau pateiktą algoritmą. , , , , , , , , , , , {1,3,4}{2}, , . Aišku, kad išskaidymų skaičius yra . 3.4.4. Sveikųjų skaičių kompozicija ir išskaidymas Nagrinėsime natūraliojo skaičiaus n išskaidymą į neneigiamų sveikųjų skaičių seką, kad . Jei skaičių tvarka sekoje yra svarbi, tai toks skaičiaus n išskaidymas vadinamas kompozicija. Šiuo atveju paprastai įvedamas apribojimas: , . Jei skaičių tvarka nesvarbi ir , tai yra multiaibė (aibė su pasikartojančiais elementais) ir vadinama skaičiaus n išskaidymu. Pavyzdžiui, jei , tai (3), (1, 2), (2, 1), (1, 1, 1) yra skaičiaus 3 kompozicija, o (3), (1, 2), (1, 1, 1) – išskaidymas. Kompozicija Nagrinėjant kompoziciją, į skaičių n patogu žiūrėti kaip į atkarpą, sudarytą iš vienetinio ilgio atkarpėlių, ir atkarpėlių susijungimo vietos pažymėtos taškais. Pavyzdžiui, kai , turėsime (žr. 3.4.2 pav.). 3.4.2 pav. Grafinis kompozicijos (2, 1, 2, 2, 1) vaizdavimas Tada kompozicijos elementai yra atstumas tarp gretimų pažymėtų taškų. 3.4.2 pav. pavaizduota skaičiaus kompozicija (2, 1, 2, 2, 1). Aišku, kad kiekvieną kompoziciją galima vaizduoti dvejetainiu skaičiumi, turinčiu skiltį: vienetinė skiltis rodo pažymėtą tašką. Pavyzdžiui, kompozicijos (2, 1, 2, 2, 1) kodas yra . n skaičiaus kompozicija, susidedanti iš k dalių, atitinka -skiltį dvejetainį skaičių, turintį vienetuką, ir todėl egzistuoja tokių kompozicijų. Išskaidymas Išskaidymas skiriasi nuo kompozicijos tuo, kad komponentų tvarka nesvarbi. Pavyzdžiui, išskaidymo atveju nedarome skirtumo tarp tokių skaičiaus 4 išskaidymų: , , . Nagrinėjant skaičiaus n išskaidymą, patogu komponentes išdėstyti didėjimo tvarka, t.y. . Skaičiaus n išskaidymą į l komponentes patogu generuoti leksikografine tvarka, pradedant išskaidymu , , ir tęsiant procesą tokiu būdu: norėdami gauti leksikografiškai didesnį išskaidymą nei nagrinėjamas, nagrinėjame elementus iš dešinės į kairę iki rasime pirmąjį elementą , tenkinantį sąlygą ; po to keičiame visiems , ir elementui pl suteikiame reikšmę . Pavyzdžiui, jei , ir nagrinėjame išskaidymą , tai gausime, kad pirmasis iš dešinės vienetukas tenkina sąlygą . Todėl kitas išskaidymas bus . Jei nei vienas išskaidymo elementas netenkina sąlygos , tai generavimo procedūra baigiama. Žemiau pateikiamas aptarto metodo algoritmas. Skaičiaus n išskaidymų generavimo leksikografine tvarka algoritmas begin l := 1; p [1] := n; p [0] := –1; while l  n do begin spausdinti ; i := l – 1; while p [l] – p [i] p [l] then begin p [l + 1] := 1; m [l + 1] := sum – p [l]; l := l + 1 end; end; { while } end; Aišku, kad pateiktas algoritmas yra tiesinis, kadangi skaičius operacijų, reikalingų pereinant nuo vieno išskaidymo prie kito, yra apribotas konstanta, nepriklausančia nei nuo n, nei nuo l. 3.5. Rekurentiniai sąryšiai 3.5.1. Rekurentinio sąryšio sąvoka ir pavyzdžiai Sprendžiant daugelį kombinatorikos uždavinių, yra naudojami rekurentiniai sąryšiai1 (lot. recurrence – grįžti). Naudodamiesi rekurentiniu sąryšiu, uždavinį su n objektų galime pakeisti uždaviniu su (n – 1) objektais, o šį – uždaviniu su (n – 2) objektais ir t.t. Paeiliui mažindami objektų skaičių, galų gale gausime uždavinį, kurį lengva išspręsti. Panagrinėkime keletą pavyzdžių. Pirmas pavyzdys: kompiuterių mokslo taikymas [MKB86] Tarkime, kad duotoje programavimo kalboje norime apskaičiuoti skaičių n ilgio išraiškų, sudarytų iš dešimties simbolių: 0, 1, 2, ..., 9 ir keturių aritmetinių veiksmų: +, –, , . Tarkime, kad šios kalbos sintaksė reikalauja, kad kiekviena išraiška baigtųsi skaitmeniu, ir dvi išraiškos gali būti jungiamos, naudojant aritmetinės operacijos simbolį. Kitaip tariant, išraiška yra seka, sudaryta iš vieno arba kelių skaitmenų arba turi formą A  B, čia A ir B – išraiškos, o simbolis  žymi aritmetinę operaciją. Pavyzdžiui, 1 + 2 ir 3  45 yra išraiškos; 1 + 2 – 3  45 taip pat yra išraiška. Tačiau 1 + + 2 nėra išraiška (du aritmetiniai simboliai negali būti šalia). Norėdami apskaičiuoti tokių n ilgio išraiškų skaičių, pasinaudosime rekurentiniu sąryšiu. Simboliu an pažymėkime nagrinėjamų n ilgio išraiškų skaičių. Visas tas išraiškas išskaidykime į dvi klases. Pirmąją klasę sudarys išraiškos, kurios (n – 1)-ojoje pozicijoje turi skaitmenį, o antrąją klasę sudarys išraiškos, kurių (n – 1)-ojoje pozicijoje yra aritmetinės operacijos simbolis. Kadangi išraiška turi baigtis skaitmeniu, tai pirmojoje klasėje bus išraiškų, t.y. kiekviena iš (n – 1) ilgio išraiškų gali būti pratęsta vienu iš 10-ties būdų. Kadangi dvi aritmetinės operacijos negali eiti kartu, tai antrojoje klasėje bus išraiškų, t.y. (n – 2) ilgio išraiška gali būti pratęsta 4 aritmetinių operacijų simboliais (n – 1)-oje pozicijoje ir 10 skaitinių simbolių n-tojoje pozicijoje. Vadinasi, . (3.5.1) Tam, kad galėtume pasinaudoti šia išraiška, reikia žinoti a0 ir a1. Aišku, kad , o , nes ilgio 1 išraiška gali būti tik skaitmuo. Tuo būdu, , , , ir t.t. Antras pavyzdys: Fibonačio skaičiai 1202 metais pasirodžiusioje knygoje ”Liber abaci” (Apie skaičiavimą) italų matematikas Fibonačis tarp kitų uždavinių pateikė tokį uždavinį. Iš triušių poros kas mėnesį gaunamas dviejų triušiukų (patinėlio ir patelės) prieauglis, o iš atvestųjų triušiukų po dviejų mėnesių jau gaunamas naujas prieauglis. Kiek triušių turėsime po metų, jei metų pradžioje turėjime vieną porą? Iš uždavinio sąlygos matyti, kad po pirmojo mėnesio turėsime dvi triušių poras. Po antrojo mėnesio turėsime tris poras, nes prieauglį davė tik pirmoji pora. Dar po mėnesio prieauglį duos ir pradinė pora, ir pora, atvesta prieš du mėnesius. Todėl iš viso bus 5 poros. Šio uždavinio sprendimui sudarysime rekurentinį sąryšį. Simboliu pažymėkime triušių porų skaičių po n mėnesių, skaitant nuo metų pradžios. Aišku, kad n-ojo mėnesio pabaigoje turėsime porą ir dar tiek naujų porų, kiek jų buvo -ojo mėnesio pabaigoje, t.y. dar . Vadinasi, . (3.5.2) Kadangi iš sąlygos matyti, kad , o , tai rekurentinis sąryšis ir šios pradinės sąlygos nusakys triušių porų skaičių: , , , , ,...,, , ... . Gauti skaičiai vadinami Fibonačio skaičiais, o jų seka – Fibonačio skaičių seka. Pastaba. Tą pačią seką gausime ir paėmę tokias pradines sąlygas , . Todėl tolesniame nagrinėjime imsime šias pradines sąlygas. Su Fibonačio skaičiais susiduriama įvairiuose kombinatorikos uždaviniuose. Jie turi įdomių savybių. Dargi yra leidžiamas žurnalas “Fibonacci Quarterly” [MKB86]. Pavyzdžiui, Fibonačio skaičių seką generuoja ir tokio uždavinio sprendinys. Reikia sužinoti, kiek yra n-narių sekų, sudarytų iš nulių ir vienetukų, kuriose nėra dviejų greta parašytų vienetų. Imkime bet kurią n-narę nulių ir vienetukų seką, tenkinančią sąlygą: du vienetai niekur joje nestovi drauge. Tokio sekos paskutinysis skaitmuo gali būti 0 arba 1. Suskirstykime nagrinėjamas n-nares sekas į dvi klases. Į pirmąją klasę talpinkime sekas, kurios baigiasi nuliu, o į antrąją – sekas, kurios baigiasi vienetu. Simboliu pažymėkime n-narių sekų, tenkinančių uždavinio sąlygą, skaičių. Aišku, kad pirmosios klasės narių skaičius bus lygus , nes n-narė seka, atmetus n-ojoje pozicijoje stovintį nulį, duos ilgio seką, tenkinančią uždavinio sąlygą. Antrojoje klasėje yra sekos, kurių n-ojoje pozicijoje yra 1. Tada, remiantis uždavinio sąlyga, teigiame, kad kiekvienos sekos -ojoje pozicijoje yra 0. Vadinasi, jei tokioje sekoje atmestume du paskutiniuosius elementus: 0 ir 1, tai gautume ilgio seką, tenkinančią uždavinio sąlygą. Vadinasi, antrosios klasės sekų skaičius yra . Tuo būdu, . (3.5.3) Kad ši rekurentinė išraiška generuotų Fibonačio skaičių seką, reikia, kad sutaptų su dviem iš eilės einančiais Fibonačio skaičiais. Aišku, kad (sekos “0” ir “1”), o (sekos “00”, “01” ir “10”). Kadangi , o , tai (3.5.3) rekurentinė išraiška generuos Fibonačio skaičius. Fibonačio skaičių savybės [Kn76] Aptarsime paprasčiausias Fibonačio skaičių savybes. 1-oji savybė: . Pastaba. Čia ir toliai vietoje simbolio naudosime simbolį . Be to, (3.5.2) išraiškos pradines sąlygas imsime , . Įrodymas. Iš Fibonačio rekurentinės išraiškos gauname: 2-oji savybė. . Įrodymas. 3-ioji savybė. . Įrodymas. Remiantis 1-ąją savybe gausime: . (3.5.4) Remiantis 2-ąją savybe gausime: . (3.5.5) Iš (3.5.4) atėmę (3.5.5), gausime: . Kadangi , tai . 4-oji savybė: . Įrodymas. Remsimės tapatybe: . (3.5.6) Tada 5-oji savybė. . Įrodymas. Įrodysime matematinės indukcijos metodu. Kai , tai . Tarkime, kad . Įrodysime, kad . 6-oji savybė. . (Įrodymas pagal indukciją.) 7-oji savybė. Sveikasis skaičius c yra ir dalikliu tada ir tiktai tada, kai jis yra skaičiaus , čia (dbd – didžiausias bendras daliklis) dalikliu. Išvada. . Trečias pavyzdys. Hanojaus bokštų uždavinys2 [DGP83] Duoti trys strypai: ir . Ant pirmojo strypo užmauta n skirtingo skersmens diskų, tenkinančių sąlygą: (žr. 3.5.1 pav.). Šiuos diskus reikia perkelti nuo strypo S1 ant kito strypo, pvz. S3, laikantis taisyklių: 1) kiekviename žingsnyje galima perkelti tik vieną viršutinį diską; 2) niekada negalima uždėti didesnio skersmens disko ant mažesnio skersmens disko; 3) bet kuriuo momentu visi diskai turi būti užmauti ant vieno iš strypų. Kiek diskų perkėlimų reikės atlikti? Simboliu pažymėkime veiksmų (disko perkėlimų) skaičių. 3.5.1 pav. Hanojaus bokštų uždavinys, kai n = 4 Tarkime, kad mokame perkelti diską. Tuomet n diskų perkeliame šiais trimis žingsniais: 1) viršutinių diskų perkeliame nuo pirmojo strypo ant antrojo, naudodamiesi laisvu trečiuoju strypu; 2) apatinį n-ąjį diską užmauname ant trečiojo strypo; 3) diskų nuo antrojo strypo perkeliame ant trečiojo naudodamiesi laisvu pirmuoju strypu. Dabar galime sudaryti rekurentinį sąryšį, nusakantį . Aišku, kad , (2.5.7) t.y. norint perkelti n diskų, reikės du kartus perkelti diskų ir dar vieną n-ąjį diską. Šio rekurentinio sąryšio pradinė sąlyga yra . (3.5.7) rekurentinis sąryšis generuos seką: ; , , ir t.t. Iš pateiktų pavyzdžių matyti, kad visi rekurentiniai sąryšiai generuoja skaičių sekas (žymėsime ), kurios priklauso tiek nuo rekurentinio sąryšio, tiek ir nuo pradinių sąlygų. Kitaip tariant, rekurentinis sąryšis su fiksuotom pradinėm sąlygom nusako natūraliojo argumento funkciją. Apibrėžimas. k-osios eilės tiesiniu rekurentiniu sąryšiu vadinsime formulę, rišančią su : čia ir yra natūraliojo argumento funkcijos ir , . Tam, kad sąryšis generuotų skaičių seką, reikia k pradinių sąlygų: . Jei yra konstantos, tai sakome, kad turime tiesinį rekurentinį sąryšį su pastoviais koeficientais. Jei , tai rekurentinis sąryšis vadinamas homogeniniu, priešingu atveju – nehomogeniniu. Pavyzdžiui, a) , b) , c) , d) , e) , f) , g) . Visos rekurentinės išraiškos, išskyrus e), f) ir g), yra tiesinės. e) išraiška nėra tiesinė, kadangi turi narį . a), b) ir d) sąryšiai yra tiesiniai su pastoviais koeficientais. Pavyzdžiui, a) ir b) sąryšiai yra 2-osios eilės, o d) sąryšis yra 3-iosios eilės. a) ir c) sąryšiai yra homogeniniai, o b) ir d) – nehomogeniniai. 3.5.2. Rekurentinių sąryšių sprendimas Turimą k-tosios eilės rekurentinį sąryšį tenkina be galo daug skirtingų sekų. Mat k pirmųjų sekos narių (pradines sąlygas) galima pasirinkti laisvai, jie nėra susieti sąryšiais. Tačiau, kai k pirmųjų narių pasirinkta, visi kiti nariai apskaičiuojami vienareikšmiškai: narys pagal rekurentinį sąryšį išreiškiamas nariais , , ..., , narys – nariais , , ..., ir t.t. Remiantis rekurentiniu sąryšiu ir pirmaisiais sekos nariais, galima vieną po kito apskaičiuoti sekos narius ir anksčiau ar vėliau surasti bet kokį sekos narį. Tačiau tokiu atveju turime apskaičiuoti ir visus pirmesniuosius narius: juk jų nežinodami, negalime rasti tolesnių narių. Tačiau dažnai reikalingas tik vienas konkretus sekos narys, o kitų narių nereikia. Todėl labai svarbu žinoti rekurentinio sąryšio sprendinį: natūraliojo argumento funkciją, kuri generuoja tą pačią seką, kaip ir rekurentinis sąryšis. Rekurentinio sąryšio sprendinį galima apibrėžti ir taip: natūraliojo argumento funkcija yra rekurentinio sąryšio sprendinys, jei ją įstatę į sąryšį, gausime tapatybę. Pavyzdys. Imkime rekurentinę išraišką . Tada yra šios išraiškos sprendinys, nes . Reikia pabrėžti, kad yra atskirasis rekurentinio sąryšio sprendinys. Apibrėžimas. k-osios eilės rekurentinio sąryšio sprendinys vadinamas bendruoju sprendiniu, jei jis priklauso nuo k laisvųjų konstantų , kurias pasirinkus galima gauti bet kurį to sąryšio sprendinį. Pavyzdžiui, sąryšio (3.5.8) bendrasis sprendinys yra (3.5.9) Iš tikrųjų, lengva patikrinti, kad (3.5.9) funkcija (3.5.8) sąryšį paverčia tapatybe. Todėl belieka patikrinti, ar kiekvieną (3.5.8) sąryšio seką galima išreikšti (3.5.9) pavidalu. Kitaip tariant, reikia parodyti, kad bet kokioms ir reikšmėms egzistuoja konstantos C1 ir C2. Įstatę (3.5.9) į (3.5.8), kai ir , gausime: Kadangi sistemos determinantas nelygus nuliui, tai ši sistema visada turi sprendinį prie bet kokių ir reikšmių. Tiesinių homogeninių rekurentinių sąryšių su pastoviais koeficientais sprendimas Rekurentiniamas sąryšiams spręsti, apskritai kalbant, bendrų metodų nėra. Tačiau labai dažnai pasitaikančių sąryšių klasė, kurią sudaro tiesiniai rekurentiniai sąryšiai su pastoviais koeficientais, sprendžiama bendru metodu. Nagrinėsime tiesinį homogeninį sąryšį su pastoviais koeficientais (HR) , čia – kokie nors skaičiai. Aptarsime tokių sąryšių sprendimą. Yra keli sprendimo metodai [MKB86]: 1) pakeitimo metodas (kitaip vadinamas iteraciniu), 2) generuojančių funkcijų metodas, 3) charakteristinių šaknų metodas, 4) neapibrėžtų koeficientų metodas. Dažniausiai naudojamas charakteristinių šaknų metodas, kurį čia ir aptarsime. Homogeninių sąryšių sprendimas Nesiaurindami klausimo, pirmiausia aptarsime 2-osios eilės su pastoviais koeficientais tiesinių homogeninių rekurentinių sąryšių sprendimo metodą. Šis metodas automatiškai taikomas ir aukštesnės eilės analogiškiems sąryšiams. Imkime 2-osios eilės su pastoviais koeficientais rekurentinį homogeninį sąryšį , (3.5.9) čia a1 ir a2 – realieji skaičiai. Tokių sąryšių sprendimas yra analogiškas homogeninių diferencialinų lygčių su pastoviaisias koeficientais sprendimui: jei turime n tiesiškai nepriklausomų diferencialinės lygties sprendinių, tai jų tiesinis darinys yra bendras diferencialinės lygties sprendinys. 1 Lema. Jei ir yra tiesiškai nepriklausomi (3.5.9) rekurentinio sąryšio sprendiniai, tai bet kokiems skaičiams – konstantoms C1 ir C2 funkcija (3.5.10) yra (3.5.9) sąryšio sprendinys. Įrodymas. (3.5.10) įstatykime į (3.5.9) sąryšį. Kairioji (3.5.9) sąryšio pusė bus lygi . Apskaičiuokime kairiąją (3.5.9) sąryšio pusę. nes ir yra atskiri (3.5.9) sąryšio sprendiniai. 2 lema. Jei r1 yra kvadratinės lygties (ši lygtis vadinama charakteristine lygtimi) šaknis, tai yra (3.5.9) išraiškos sprendinys. Įrodymas. Kadangi r1 yra charakteristinės lygties šaknis, tai . Šią lygybę padauginę iš , gausime: , t.y. yra (3.5.9) sprendinys. Teorema. (3.5.9) rekurentinio sąryšio bendrasis sprendinys apskaičiuojamas taip: 1) randame charakteristinės lygties šaknis r1 ir r2, 2) bendrąjį sprendinį užrašome: , jei , , jei . Šios teoremos teisingumas tiesiogiai išplaukia iš 1-osios ir 2-osios lemos ir to fakto, kad yra (3.5.9) sprendinys, jei . Be to, kadangi ir yra tiesiškai nepriklausomi, tai konstantos C1 ir C2 egzistuoja prie bet kokių ir reikšmių. Kaip minėjome aukščiau, k-osios eilės rekurentinė išraiška sprendžiama analogiškai. Čia reikia įvertinti tik tą faktą, kad, jei charakteristinės lygties šaknys , tai atskirieji tiesiškai nepriklausomi rekurentinio sąryšio sprendiniai yra , , ..., . Pirmas pavyzdys. Išspręskime Fibonačio seką nusakantį rekurentinį sąryšį: , , . Sudarome charakteristinę lygtį . Šios lygties šaknys yra , . Vadinasi, bendrasis sprendinys yra . Konstantas C1 ir C2 parinksime taip, kad jos atitiktų pradines sąlygas: , . Gausime , . Iš šios lygčių sistemos gausime: . Vadinasi, Fibonačio seką generuoja tokia natūraliojo argumento funkcija . Seka yra glaudžiai susijusi su auksinio piūvio santykiu . Primename, kad atkarpa (žr. 3.5.2 pav.) auksiniu piūvio santykiu daloma į dvi dalis a ir b taip, kad . 3.5.2 pav. Auksinio piūvio santykis Paėmę , gausime , , . Kadangi dalo atkarpą vidiniu dalijimu, tai . Simboliu žymėsime , t.y. . Vadinasi, Fibonačio seką galima užrašyti taip: . Kadangi , tai . Pasirodo (žr [Kn76]), kad, kai , , apvalinant iki artimiausiojo sveikojo skaičiaus. Pavyzdžiui, Fibonačio skaičių seka yra: ir t.t. Paėmę , gausime: . Suapvalinę gausime 2. Paėmę , gausime . suapvalinę gausime 3. . Paėmę , gausime . suapvalinę gausime 5. Antras pavyzdys. Išspręskime trečiosios eilės rekurentinį homogeninį sąryšį: , kai , , . Sąryšio rekurentinė lygtis yra . Šios lygties šaknys yra: , ir . Tada sąryšio bendrasis sprendinys yra . Apskaičiuosime konstantas: Išsprendę lygčių sistemą, gausime , ir . Vadinasi, nagrinėjamo rekurentinio sąryšio su nurodytomis pradinėmis sąlygomis sprendinys yra . Nehomogeninių sąryšių sprendimas Panagrinėkime tiesinių nehomogeninių rekurentinių sąryšių su pastoviais koeficientais (NHR) sprendimą, kuris yra visiškai analogiškas tiesinių nehomogeninių diferencialinių lygčių su pastoviais koeficientais sprendimui. Teorema. Tarkime, kad NHR turi pavidalą . Tarkime, kad HR yra nagrinėjamo NHR homogeninis sąryšis. Tada NHR bendrasis sprendinys randamas taip: 1) apskaičiuojamas HR bendrasis sprendinys , 2) apskaičiuojamas NHR atskirasis sprendinys , 3) šių sprendinių suma ir yra bendrasis NHR sprendinys: . Pirmas pavyzdys. Raskime bendrąjį NHR , , sprendinį. Pirmiausia rasime HR sprendinį. Šios HR charakteristinė lygtis yra , o šaknys , . Tada . Apskaičiuosime atskirąjį NHR sprendinį. Jo ieškosime laisvojo nario pavidale: . Įstatę į NHR, gausime , , , , . Vadinasi, . Tada NHR bendrasis sprendinys yra . (3.5.10) Tarkime, kad turime tokias pradines sąlygas: , . Apskaičiuosime C1 ir C2. Į (3.5.10) formulę įstatę ir , gausime: Išsprendę lygčių sistemą, gausime: , o . Vadinasi, . Antras pavyzdys. Išspręskime Hanojaus bokštų rekurentinį sąryšį: , . Hanojaus bokštų HR yra . Tada charakteristinė lygtis yra , ir . HR bendrasis sprendinys bus . Kadangi 1-tas nėra charakteristinio polinomo šaknis, tai atskirojo NHR sprendinio ieškosime laisvojo nario pavidale . Apskaičiuosime C statydami į NHR. . Iš čia . Vadinasi, . (3.5.11) Apskaičiuosime C1 įstatydami į (3.5.11). Gausime: , . Tokiu būdu . Atskiro NHR sprendinio parinkimas Kaip minėjome aukščiau, atskiro NHR sprendinio ieškosime pavidale, kuris priklauso nuo nehomogeninio rekurentinio sąryšio laisvojo nario formos ir nuo HR charakteristinės lygties šaknų. Nagrinėjame nehomogeninį rekurentinį sąryšį , esant duotoms pradinėms sąlygoms, t.y. reikšmėms. NHR atskirojo sprendinio pavidalas, kai , čia D ir a – konstantos. Šiuo atveju atskirojo sprendinio ieškosime pavidale čia ir toliau yra HR, atitinkančio nagrinėjamąjį NHR, charakteristinis polinomas, t.y. . Pirmas pavyzdys. Spręskime NHR: , , . Charakteristinis polinomas yra ir jo šaknys yra: , . Tada . Kadangi šiame pavyzdyje ir a nėra charakteringojo polinomo šaknis, tai ieškosime pavidale . Įstatę į NHR, gausime, kad . Tuo būdu bendras NHR sprendinys . Įvertindami pradines sąlygas: , , gausime sistemą: kurios sprendinys yra , . Vadinasi, . Antras pavyzdys. Išspręskime NHR: . HR charakteristinė lygtis yra ir jo šaknys yra: , . Todėl HR bendrasis sprendinys yra . Kadangi 2 yra charakteristinės lygties du kartus kartotinė šaknis, tai ieškosime pavidale: . Įstatę šią išraišką į NHR, gausime: . , , , . Vadinasi, yra NHR bendrasis sprendinys. Teorema. Tarkime, kad yra atskirasis NHR sprendinys, o yra atskirasis NHR sprendinys, tai yra atskirasis NHR sprendinys. Pavyzdys. Raskime NHR atskirąjį sprendinį. Pirmiausia rasime atskirąjį sprendinį , po to – atskirąjį sprendinį ir juos sudėsime. Nesunku įsitikinti, kad , o . Vadinasi, nagrinėjamosios NHR atskirasis sprendinys yra . NHR atskirojo sprendinio pavidalas, kai yra polinomo ir eksponentės sandauga: , čia ir a – konstantos. Šiuo atveju atskirojo sprendinio pavidalas čia . Pavyzdys. Išspręskime NHR , . Charakteristinio polinomo šaknys yra , . Kadangi 4 nėra šaknis, tai . Įstatę šį sprendinį į NHR, gausime: Sudauginę ir sutraukę panašius narius, gausime: . Palyginę koeficientus prie tų pačių n laipsnių, gausime sistemą kurios sprendinys yra: , , . Vadinasi, . NHR atskirojo sprendinio pavidalas, kai yra polinomas, t.y. . Nesunku pastebėti, kad tai polinomo ir eksponentės sandaugos atskirasis atvejis, kai . Vadinasi, Pavyzdys. Raskime išraiškai . Kadangi 1-tas yra du kartus kartotinė charakteristinio polinomo šaknis, tai . Įstatę į NHR, gausime: , . Tuo būdu bendrasis NHR sprendinys yra . Išnagrinėtus atvejus galima sutraukti į 9 lentelę. Iš pateikto nagrinėjimo galime padaryti išvadą, kad NHR atskirojo sprendinio išraiška priklauso nuo NHR laisvojo nario – funkcijos , tačiau turi būti tiesiškai nepriklausomas nuo HR sprendinio . 9 lentelė. NHR atskirieji sprendiniai – charakteristinis polinomas NHR atskirojo sprendinio pavidalas a yra m kartų kartotinė šaknis a yra m kartų kartotinė šaknis 1 yra m kartų kartotinė šaknis 3.6. Generuojančios funkcijos Kombinatorinių uždavinių, kuriuose reikia apskaičiuoti skaičių objektų, tenkinančių nurodytas sąlygas, sprendinys dažnai būna seka , čia – ieškomų k “matavimų” objektų skaičius. Pavyzdžiui, jei ieškome skaičiaus n išskaidymo, tai yra skaičiaus n išskaidymo į k dėmenis variantų skaičius; jei nagrinėjame n-elementės aibės išskaidymą į poaibius, tai ir t.t. Šiais atvejais sekai patogu priskirti formalią eilutę (3.6.1) kuri vadinama šią seką generuojančia funkcija. Pavadinimas “formalioji eilutė” reiškia, kad (3.6.1) eilutę traktuosime kaip sekos patogų užrašą. Šiuo atveju nesvarbu, prie kokių x reikšmių ši eilutė konverguoja. Todėl mes niekada neskaičiuosime tos eilutės sumos prie konkrečios x reikšmės. Su šiomis eilutėmis mes vykdysime konkrečias operacijas ir palyginsime koeficientus prie tų pačių x laipsnių. Tarkime, turime dvi eilutes: ir . Apibrėšime šių eilučių sumą. . Apibrėšime sandaugos iš pastovaus skaičiaus operaciją. . Apibrėšime šių eilučių sandaugą. , čia . Jei , kai , tai (3.6.1) eilutę sutapatinsime su daugianariu: . Aptarsime, kaip laipsninė eilutė dalijama iš kitos laipsninės eilutės. Padalinę eilutę iš , gausime eilutę . Tada pagal dalybos veiksmo apibrėžimą galima parašyti (3.6.2) (3.6.2) formulėje palyginę koeficientus prie tų pačių x laipsnių, gausime: (3.6.3) Tos lygybės sudaro begalinę lygčių sistemą, iš kurios reikia rasti koeficientus ir t.t. Iš (3.6.3) nesunku apskaičiuoti koeficientus c: (3.6.4) Iš matematinės analizės žinome, kad, jei eilutė kažkurioje nulio aplinkoje konverguoja, tai (3.6.1) eilutė yra funkcijos Makloreno eilutė. Šiuo atveju generuojanti funkcija yra matematinės funkcijos Makloreno eilutė. Todėl, šiuo atveju, atliekant operacijas, vietoje eilutės galima imti analitinę funkciją . Pavyzdžiui, galime rašyti: , (3.6.5) ir t.t. Apskaičiuokime kai kurių sekų generuojančias funkcijas. Imkime seką , čia , kai , yra lygus 0. Šios sekos generuojanti funkcija yra Niutono binomas, t.y. , (3.6.6) Panagrinėkime (3.6.6) formulės fizinę prasmę. Kiekvieną daugiklį galima traktuoti kaip aibės atitikmenį, kuris nusako elemento pasirodymo skaičių X poaibyje: 0 kartų (dėmuo ) ir vieną kartą (dėmuo ). Aišku, kad kiekvienas aibės X poaibis vienareikšmiškai apibrėžiamas, nurodant, kiek kartų kiekvienas elementas pasirodo poaibyje, t.y. iš kiekvieno daugiklio išrenkant po vieną dėmenį. Vadinasi, šios sandaugos koeficientas prie x k-tojo laipsnio ir parodo aibės X k-elemenčių poaibių skaičių. Aišku, kad šį nagrinėjimą galima apibendrinti nagrinėjant aibes su pasikartojančiais elementais. Pavyzdžiui, imsime aibę , ir simboliu pažymėsime šios aibės k-elemenčių poaibių skaičių. Apibendrinus aukščiau pateiktus samprotavimus, sekos generuojanti funkcija yra Iš šios funkcijos matosi, kad skaičius poaibių, turinčių 5-is elementus, yra 22. Nesunku suvokti, kad, atitinkamai parinkus i-ąjį daugiklį, galima įvesti įvairius apribojimus elementui ai. Pavyzdžiui, jei šis daugiklis yra , tai reiškia, kad poaibyje elementas ai gali pasirodyti 0, 3, arba 7 kartus; jei daugiklis yra , tai reiškia, kad elementas ai poaibyje gali pasirodyti lyginį skaičių kartų. Jei mes neįvedame jokio apribojimo elemento ai, , pasirodymo skaičiui, tai generuojanti funkcija yra Aišku, kad aukščiau pateiktiems pavyzdžiams galima suteikti ir kitokią interpretaciją. Pavyzdžiui, nagrinėkime lygtį , čia e1, e2, ir r – natūralieji skaičiai. Skaičiams e1 ir e2 gali būti įvesti apribojimai. Mus domina šios lygties sprendinių skaičius. Tarkime, e1 gali būti arba 0, arba 1, arba 9, o e2 tenkina nelygybę . Simboliu , pažymėkime šios lygties sprendinių skaičių. Tada šios sekos generuojanti funkcija yra dėmenų e1 ir e2 apribojimus nusakančių funkcijų ir sandauga: . Šį pavyzdį galima apibendrinti imant lygtį: , ei, r – natūralieji skaičiai. Norint sužinoti šios lygties sprendinių skaičių, kai ei, , tenkina apribojimus , turime sudaryti generuojančią funkciją: ir koeficientas prie duos atsakymą. Imkime seką . Šios sekos generuojanti funkcija yra (žr. (3.6.5) formulę). Remiantis tuo, kad analitinę funkciją galima panariui diferencijuoti, išveskime sekos ,... generuojančią funkciją. Žemiau pateikiame lentelę, kurioje surašytos kai kurių sekų generuojančios funkcijos. 10 lentelė. Generuojančios funkcijos Eil. nr. Sekos Generuojančios funkcijos 1 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 3.7. Rekurentiniai sąryšiai ir generuojančios funkcijos Kaip minėjome, rekurentiniai sąryšiai generuoja skaitines sekas, o šioms galima užrašyti generuojančias funkcijas. Šiame paragrafe panagrinėkime, kaip, turint tiesinį rekurentinį sąryšį, sudaryti jam atitinkančią generuojančią funkciją. Tam tikslui panagrinėkime taisyklingąją algebrinę trupmeną , čia ir – atitinkamai n-osios ir m-osios () eilės polinomai: , , ir . Aišku, kad (3.7.1) Vadinasi, Sudauginę (3.7.1) dešiniąją pusę ir palyginę koeficientus prie tų pačių x laipsnių, gausime (3.7.2) čia didžiausia galima n reikšmė yra . Visi tolesni sąryšiai bus vienodo pavidalo: . (3.7.3) Vadinasi, (3.7.1) eilutės koeficientai tenkina (3.7.3) tiesinį rekurentinį sąryšį, o (3.7.2) apibrėžia šio rekurentinio sąryšio pradines sąlygas. Atvirkščiai, tarkime, kad duotas m-osios eilės (3.7.3) rekurentinis sąryšis ir pradinės sąlygos . Tada šiam sąryšiui atitinkanti generuojanti funkcija yra trupmena (3.7.4) čia – rekurentinio sąryšio koeficientai, o – koeficientai, apskaičiuoti iš (3.7.2) lygčių. Pastaba. Tarkime, , čia – polinomo šaknys. Tada (3.7.1) eilutė konverguoja srityje . Pavyzdys. Sudarysime Fibonačio skaičių sekos generuojančią funkciją. Fibonačio skaičius generuojantis rekurentinis sąryšis yra . Vadinasi, Fibonačio skaičius generuojanti funkcija yra . Koeficientus a0 ir a1 apskaičiuosime pagal (3.7.2) formules: Tuo būdu, Fibonačio skaičių sekos generuojanti funkcija yra . Iš pirmo žvilgsnio atrodo, kad mažai ką laimėjome, rekurentinį sąryšį pakeisdami generuojančia funkcija: juk vis tiek reikės skaitiklį dalyti iš vardiklio, o iš to gausime tą patį rekurentinį sąryšį. Tačiau (3.7.4) trupmeną galima tapačiai pertvarkyti, o tai palengvina skaičių ck radimą. Pavyzdys. Tarkime, generuojanti funkcija yra . Išdėstykime šią trupmeną paprastesnėmis trupmenomis. Šis uždavinys buvo spręstas matematinės analizės kurse. Tam tikslui raskime vardiklio polinomo šaknis: . Vadinasi, . Abi lygybės puses padauginę iš bendro vardiklio ir palyginę skaitiklių koeficientus prie tų pačių x laipsnių, gausime: Šios sistemos sprendinys yra: , , ir . Trupmenos eilutė žinoma. Pavyzdžiui, . Tokiu būdu, gausime: Apskaičiavę koeficientą prie , gausime: . Tuo pačiu gavome generuojančiai funkcijai atitinkančio rekurentinio sąryšio sprendinį. Šis nagrinėjimas duoda mintį, kaip galima spręsti rekurentinį sąryšį, panaudojant generuojančias funkcijas. Tam tikslui reikia: 1) sudaryti rekurentiniam sąryšiui generuojančią funkciją , 2) išreikšti elementariųjų trupmenų suma, o jas – laipsninėmis eilutėmis (pagal Niutono formulę), 3) gautos eilutės koeficientas prie ir bus ieškomasis sprendinys. Pavyzdys. Išspręskime rekurentinį sąryšį: , , . Šiuo atveju , ir . Pagal (3.7.2) formules apskaičiuosime a0 ir a1: Vadinasi, rekurentinį sąryšį atitinkanti generuojanti funkcija yra . Ši trupmena elementariosiomis trupmenomis išreiškiama taip: , ir, išskaidę eilute, gausime: . Todėl . Reikia pabrėžti, kad rekurentinių išraiškų sprendimas charakteristinių šaknų metodu yra žymiai efektyvesnis nei generuojančių funkcijų metodas.

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!