Rekurentiniai s¹ryšiai

Rekurentiniai s¹ryšiai

Rekurentinio s¹ryšio s¹voka ir pavyzdžiai

Sprendžiant daugelį kombinatorikos uždavinių, yra naudojami rekurentiniai s¹ryšiai (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 a_n 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 a₀ ir a₁. 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ždavinys[2] 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ų:

kiekviename žingsnyje galima perkelti tik vien¹ viršutinį disk¹;

niekada negalima uždėti didesnio skersmens disko ant mažesnio skersmens disko;

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:

viršutinių diskų perkeliame nuo pirmojo strypo ant antrojo, naudodamiesi laisvu trečiuoju strypu;

apatinį n-¹jį disk¹ užmauname ant trečiojo strypo;

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.

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 C₁ ir C₂.

Į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]:

pakeitimo metodas (kitaip vadinamas iteraciniu),

generuojančių funkcijų metodas,

charakteristinių šaknų metodas,

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 a₁ ir a₂ – 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 C₁ ir C₂ 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 r₁ yra kvadratinės lygties

(ši lygtis vadinama charakteristine lygtimi) šaknis, tai yra (3.5.9) išraiškos sprendinys.

Įrodymas. Kadangi r₁ 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:

randame charakteristinės lygties šaknis r₁ ir r₂,

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 C₁ ir C₂ 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 C₁ ir C₂ 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:

apskaičiuojamas HR bendrasis sprendinys ,

apskaičiuojamas NHR atskirasis sprendinys ,

š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 C₁ ir C₂. Į (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 C₁ į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