Kombinatorika

1.Naturalieji skaiciai. Matematines indukcijos principas

Nepriestaringumo desnis. Du vienas kitam priesingi teiginiai p ir ¯p vienu metu negali buti teisingi (p^¯p=0)

Treciojo negalimo desnis. Is dvieju priesingu teiginiu p ir ¯p vienas visada yra teisingas (p^¯p=1).

Apibrezimas. Naturaliaisiais skaiciais vadiname netuscios aibes N elementus, jeigu tarp kai kuriu is ju

egzistuoja sarysis ,,a‘ eina po a“, tenkinantis aksiomas:

1) egzistuoja skaicius (vadinamas vienetu), neinantis po jokio kito skaiciaus;

2) po kiekvieno skaiciaus eina tik vienas skaicius;

3) kiekvienas skaicius eina ne daugiau kaip po vieno skaiciaus;

4) aibes NN poaibis M sutampa su pacia aibe N, jei jis turi tokias savybes:

a) 1 $ M,

b) jeigu skaicius a priklauso M, tai ir po a einantis skaicius a‘ taip pat priklauso aibei M

Matematines indukcijos principas

Tegu p(n) – kazkoks teiginys apie naturaluji skaiciu n. Tarkime, kad p(1) yra teisingas, ir is prielaidos, kad p(n) yra teisingas, sugebame isvesti, kad p(n‘) irgi yra teisingas. Darome isvada: teiginys p(n) yra teisingas visiems n $ N.

Archimedo aksioma. Bet kuriai naturaliuju skaiciu porai a, bb galima rasti toki naturaluji skaiciu n, kad an>b.

Maziausiojo elemento principas. Kiekvienas netuscias naturaliuju skaiciu aibes poaibis turi maziausia elementa.

Dirichle (P.G.L. Dirichlet, 1805–1859) principas. Jei m rutuliu yra sudeti i n < m deziu, tai bent vienoje dezeje yra 2 aar daugiau rutuliu.

2.Dauginimo tasykle

Dekarto ( Rene Descartes, 1596–1650) sandauga. Tai sutvarkytuju poru aibe.

A × B = {(ai, bj) : ai e A, bj e B, 1 ≤i ≤ n, 1 ≤ j≤ m}

1 teorema. |A × B| = |A| |B|.

2 teorema. Jei abecele A turi n raidziu, tai galime sudaryti n^k zodziu, kuriu ilgis yra k.

3 teorema. Aibes A = {a1, . . . , an} poaibiu, iskaitant ir tusciaji, skaicius lygus 2^n.

|>Nagrinekime visu poaibiu aibes atvaizdi aibeje, sudarytoje is n zodziu su ,,raidemis“ 0, 1. Sis atvaizdis apibreztas taip: A ] P = {ai1 , . . . , aik} 7! (0 . . . , 0, 1, 0 . . . , 0, 1, 0, . . . 00) cia ,,raide“ 1 irasyta is-oje pozicijoje pabreziant, kad is-asis aibes A elementas patenka i poaibi P. Atvaizdis yra bijekcija. Pagal 2 teorema siu zodziu aibes galia lygi 2^n ir sutampa su k poaibiu aibes galia.<|

4 teorema. Jei X = {x1, . . . , xn} ir Y = {y1, . . . , ym}, tai funkciju f : X ->aibes galia lygi m^n.

|>Kiekviena funkcija f : X ->galime vienareiksmiskai isreiksti vektoriumi (f(x1),.,f(xn)). Kadangi dabar ,,raide“ f(xj ), 1≤ jj≤ n, imama is abeceles Y, turincios m raidziu, teoremos teiginys isplaukia is 2 teorem. <|

Sioje teoremoje isvesta formule paaiskina daznai naudojama zymeni {f : X ->Y } =: Y^X .

3. Gretiniai, keliniai ir deriniai

1 teorema. Ak/n = n(n − 1)(n − 2) • • • (n − k + 1).

2 teorema. Deriniu is n po k skaicius lygus Ck/n = (Ak/n)/k!= n!/(k!(n − k)!)

Mokslineje literaturoje vartojami ir tokie deriniu is n po k zymemys: (n//k)= (n//(k, n − k))

Paimtas is n aibes k elementu rinkinys su galimais pasikartojimais vadinamas kartotiniu sios aibes k deriniu. Ju skaicius Hk/n = Ck/(n+k−1)=((n+k−1)//k)

4. Kartotiniai gretiniai

Teorema. Polinominiu koeficientu formule yra (n//(p1, . . . , pk))

|>Dauginkime panariui n nezinomuju sumu, imdami xi1 is pirmosios sumos, xi2 is antrosios sumos ir t.t., xin is n-osios sumos ir sudekime visas sandaugas

(2) xi1 • • • xin. Kadangi ij 2 {1, . . . , k}, 1 ≤ j ≤ n, tai turesime k^n sandaugu (visus n zodzius is k raidziu x1, . . . , xk). Sudedant (2) sandaugas, reikia sutraukti panasius narius. Jie bus to paties pavidalo, t.y.

(3) xp1/1 • • • xpk/k, nusakomo vektoriumi ¯p. Kiek tokiu panasiu nariu kaip (3)? Raide x1 ((2) sandaugoje galejo uzimti p1 poziciju is n galimu, t.y. buvo (n//p1) budu, x2 – ((n−p1)//p2 ) budu ir t.t. Tesdami si procesa, gautume (n//p1)• ((n−p1)//p2)•••((n−p1−p2−•• •− pk−1)//pk )= n!/(p1! . . . pk!)

Cia pasinaudojome binominio koeficiento formule.<|

5. Binominiu koeficientu tapatybes

Patogu isplesti binominio koeficiento apibrezima:

(z//k)= { 1.(z(z−1).(z−k+1))/k! , kai z e C, k e N U {0},2.0, kai k < 0.

1 teorema. (n//k)= ( n//(n − k)), 0≤k≤n.

2 teorema.Hk/n = ((n + k − 1)//k )= (−1)^k*(-n//k ), 0≤k≤n.

3 teorema.(n//k)*(k//m)=(n//m)*((n − m)//(k − m)), 0≤m≤k≤n.

4 teorema (Paskalio tapatybe).(n//k)=((n − 1)//(k − 1))+((n − 1)//k), 0≤ k≤n, ((n − 1)//n)= 0.

5 teorema. (n ∑k=0) ((r + k)//k)=((r + n + 1)//n).

6 teorema (Ortogonalumo sarysis) Tegu δmn – Kronekerio simbolis, t.y. δnn = 1ir δmn = 0, kai m≠n. Jei m≤n, tai Snm :=(n∑k=m)(−1)^k(n//k)*(k//m)= (−1)^mδmn.

|>Pagal 3 teorema Snm =(n∑k=m)(−1)^k(n//m)*((n − m)//(k − m))=(n//m)(n∑k=m)(−1)*k((n − m)//(k − m))

Pakeiskime sumavimo indeksa k − m = j ir gausime Snm = (n//m)(n−m∑j=0)(−1)^(j+m)((n−m)//j) = (−1)^m(n//m)(1 − 1)^(n−m) = 0,jei m≠n.<|

7 teorema (Apgrezimo sarysis) Tegu ak, bk, 0≤k≤n – dvi skaiciu sekos. Is vienos is siu lygybiu bn = (n∑k=0)(−1)^k(n//k)ak, an = (n∑k=0)(−1)^k(n//k)bk isplaukia antroji.

|>Jei teisinga pirmoji lygybe, tai istatydami patikriname antraja. Skaiciuojame keisdami sumavimo tvarka ((n∑k=0)(−1)^k(n//k)bk =(n∑k=0)(−1)^k(n//k)*(k∑m=0)(−1)^m(k//m)am = (n∑m=0)(−1)^m*am (n∑k=m)(−1)^k (n//k)*(k//m) = anδnn = an. Paskutiniame zingsnyje pritaikeme ortogonalumo sarysi (6 teorema). <|

8 teorema (Harmoniniu skaiciu savybe). 1+1/2+ • • • +1/n = (n∑k=1)(−1)^(k+1)(n//k)*1/k.

|> Desiniojoje lygybes puseje esanciam binominiam koeficientui pritaikykime Paskalio lygybe. Gauname hn := (n∑k=1)(−1)^(k+1)(n//k)1/k = (n∑k=1)(−1)^(k+1)(((n − 1)//k)+((n − 1)//(k − 1))1/k = hn−1 + (−1)^(n+1) ((n − 1)//n)1/n + (n∑k=1)(−1)^(k+1)((n − 1//(k − 1))1/k (1) Antrasis demuo lygus nuliui, skaiciuojame treciaji. Jis lygus (n∑k=1)(−1)^(k+1) ((n − 1)!)/(k!(n − k)!) = −1/n (n∑k=1)(−1)^k(n//k) = −1/n[(1 − 1)^n − 1] = 1/n. Istate i (1) lygybe gauname rekurentuji sarysi hn = hn−1 + 1/n. Kadangi f1 = 1, pagal matematines indukcijos principa is jo isplaukia hn = 1 + 1/2+1/3+ • • • +1/n. <|

6. Recio principas

Skaiciuosime skaiciu elementu, patenkanciu i keletos gal but persikertanciu aibiu sajunga. Apibendrinsime nesunkiai suvokiamas formules |AUB| = |A| + |B| − |A∩B| ir (1) |AUBUC| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.

1 teorema.|A1U • • •UAn| = S1 − S2 + S3 + • • • + (−1)^(n+1)Sn.

|> Pazymekime U = A1U• • •UAn. Fukcija IA : U -> {0, 1} vadinsime poaibio A C U indikatoriumi, jeigu IA(x) =

1 tada ir tik tada, kai x e A. Vadinasi, |A| = (∑x2U)IA(x). Todel a(i) = (∑x2U)IAi (x), a(i, j) =(∑x2U)

IAi∩Aj (x), . . . , a(i1, . . . , ik) =(∑x2U)IAi1 ∩•••∩Aik(x), 1≤iJei ¯Ai := X Ai, tai nagrinejamas skaicius lygus |¯ A1∩• • •∩¯An| = |X (A1U• • •UAn)| = |X| − |A1U ••• UAn|.Toliau pakanka pritaikyti 1 teorema. <|

7. Netvarku uzdavinys

Teorema. Netvarkinguju keitiniu skaicius lygus n!(n∑k=0)((−1)^k)/k! .

|>Bendras keitinio pavidalas ((1 2 . . . n)//(i1i2 .. . . in)). Tegu Ak – aibe keitiniu su savybe ik = k, X – visa keitiniu aibe, o ¯Ak = XAk, 1≤k≤n. Ieskomasis skaicius pagal 6.2 teorema lygus |¯A1∩ ••• ∩¯An| = |X| −

(n∑i=1)|Ai| + (∑1≤iJei U – visu atvaizdziu aibe, tai |U| = mn. Tegu Y = {y1, . . . , ym}, o Aj – atvaizdziai, neigyjantys reiksmes yj , 1≤j≤m. Pagal ta pacia atvaizdziu skaiciaus teorema gauname |Aj | = (m − 1)^n, |Ai∩Aj| = ((m − 2)^n, . . . , |Ai1∩•••∩Aik| = (m − k)^n. Cia 1≤i< j≤m, 1≤i1 < i2 • • • < ik≤m. Siurjekciju vaizdai yra visi yj , todel mus dominanti aibe yra lygi aibiu Aj papildiniu iki U ssankirtai, t.y., S :=¯A1∩¯A2∩•••∩¯An. Pagal praeito skyrelio teoremos isvada (1) |S| = |U| − S1 + S2 − • • • + (−1)^mSm. Cia S1 = (m//1) * (m−1)^n, S2 = (m//2) * (m−2)^n, . . . , Sm−1 = (m//(m − 1)) * (m−m+1)^n, Sm = 0. istate i (1) formule, baigiame irodyma <|

Isvada. n! = (n∑k=0)(−1)^k (n//k) * (n − k)^n, n≥1.

|> Kiekviena n aibes siurjekcija i ja pacia yra ir bijekcija, o bijekciju skaicius sutampa su n keitiniu kiekiu. Toliau pritaikome teorema, kai n = m <|

9. Stirlingo skaiciai

Aibes A skaidiniu (k skaidiniu) vadiname israiska (1) A = A1U•••U Ak, AjCA, Aj ≠ (tuscia aibe); Ai∩Aj = (tiscia aibe), 1≤i Jei A = {a1, . .. . , an}, f e Q(n, k), tai pazymeje Aj = {ai e A : f(i) = j}, 1≤j≤k, gauname vieninteli skaidiniA = A1U.Ak. Atvirksciai, turedami toki skaidini, galetume apibrezti daug siurjekciju. Pakaktu aibes Aj elementus atvaizduoti i viena skaiciu ij taip, kad skaiciai i1, . . . , ik sudarytu k kelini. Kadangi tokiu keliniu yra k!, is viso gautume k! siurjekciju. Taigi |Q(n, k)| = k!S(n, k). Toliau pakanka pritaikyti (2) formule <|

Jei Bn – visu galimu AA israisku, jungiant netuscius poaibius, skaicius, vadinamas Belo skaiciumi, tai Bn = (n∑k=1)S(n, k).

2 teorema. Susitarkime, kad S(0, 0) = 1. Tada S(n, k) = kS(n − 1, k) + S(n−1, k−1), 1≤k< n.

|> Panasiai kaip ir Paskalio teoremos irodyme, visus aibes A k skaidinius perskirkime i dvi dalis. Viena dali sudarykime is tokiu skaidiniu, kuriuose vienas is jungiamu poaibiu yra {n}. Ju pavidalas bus toks: A = A1U.Ak−1U {n}. Cia poaibiuose Aj , 1≤k−1, nera n. Tokiu skaidiniu bus S(n−1, k−1).

Kita dali sudarantys likusieji skaidiniai gali buti gauti tokiu budu. Imkime aibes {1, . . . , n − 1} k skaidinius {1, . . . , n − 1} = A‘/1U•••UA‘/k, kuriu bus S(n−1, k), ir prijungdami paeiliui n prie A‘/j , 1≤j≤k, is kiekvieno tokio skaidinio padarytume k pradines aibes A skaidiniu. Todel antroje skaidiniu grupeje yra kS(n−1, k) A skaidiniu. Sudeje abieju klasiu skaicius, gauname S(n, k). <|

Isvada. Jei 1≤ k≤n, tai S(n, k) ≤k^(n+1). Irodyti, pagal indukcija.

3 teorema. Jei S(n, 0) := 0, kai n e N, ir S(0, 0) = 1, tai x^n =(n∑k=0)S(n, k)(x)k, x e R, n≥0, 0^0 := 1.

|>Atvejis n = 0 yra trivialus. Tegu toliau n e N. Irodinejamos lygybes ppusese yra n laipsnio polinomai, todel pakanka ja patikrinti daugiau negu n tasku. Irodysime, kad ji teisinga su visais naturaliaisiais x≥n. Tuo tikslu, nagrinejame atvaizdzius g : A -> X := {1, 2, . . . , x}. Ju yra xn. Si kieki skaiciuojame kitu budu. Tegu Y = g(X) C X – funkcijos g reiksmiu aibe. Tada g : A -> Y yra siurjekcija. Poaibiuose Y gali buti 1, 2, . . . , n elementu. Jei |Y | = k, tai gausime |Q(n, k)| skirtingu siurjekciju, atitinkanciu skirtingus atvaizdzius g. Pakeite Y C X, vel gautume skirtingas siurjekcijas bei atvaizdzius. Vadinasi, visas atvaizdziu g skaicius gali buti uzrasomas sitaip: xn = (n∑k=1)( ∑Y _X, |Y|=k)|Q(n, k)|. Pagal 2 teorema x^n = (n∑k=1)( ∑Y _X, |Y |=k)S(n, k)k! = (n∑k=1)S(n, k)k! (∑ Y _X, |Y |=k)1 =(n∑k=1) S(n, k)(x)k, nes aibe X turejo (x//k) skirtingu k poaibiu. Jei n e N, pagal susitarima S(n, 0) = 0, todel pastarojoje sumoje galetume prijungti nulini demeni, atitinkanti k = 0. Taip gautume teoremoje nurodyta formule <|

Formule (x)n = (n∑k=0)s(n, k)x^k, x e R, apibrezia pirmos rusies Stirlingo skaicius s(n, k).

4 teorema (Ortogonalumo sarysis) (n∑k=m)S(n, k)s(k,m) = δmn, m, n≥0.

|> Pasinaudokime auksciau nnagrinetu polinomu israiskomis per Stirlingo skaicius. Gauname x^n =

(n∑k=1)S(n, k)(x)k = (n∑k=1)S(n, k) * ((k∑m=0) s(k,m)x^m) = (n∑m=0)((n∑k=m)S(n, k)s(k,m))x^m. Palygine polinomu koeficientus prie vienodu x laipsniu, baigiame 4 teoremos irodyma <|

Rekuriancioji Belo formule: Bn = (n∑k=1) ((n − 1)//(k − 1))Bn−k, n e N.

10. Skirtumo operatorius

Δ^m =Δ(Δ^(m−1)), kai m >=0, Δ^1= Δ; Δ^0 = I, cia I tapatusis atvaizdis.

1 teorema. Bet kokiai funkcijai f(x) ir m >= 0 teisingos tapatybes

1) Δ^m f(x) =(mΣk=0)(−1)^k (m//k) f(x + m − k) =(mΣk=0)(−1)^(m−j) (m//j) f(x + j),

2) f(x) =(mΣk=0)(−1)^k(m//k)Δ^k f(x)

3) f(x + m) =(mΣk=0)(m//k)Δ^k f(x)|>Pirmoji is (1) lygybiu irodoma matematines indukcijos pagalba, pasinaudojant Paskalio tapatybe. Patikrine (1) su m = 0, 1 ir tare kad ji si lygybe yra teisinga del m−1>=1, skaiciuojame suma Sm:=(mΣk=0)(−1)^k(m//k)* *f(x+m−k)=(mΣk=0)(−1)^k(m−1//k)f(x+m−k)+ +(mΣk=0)(−1)^k(m−1//k−1)f(x+m−k). Gautose sumose atmete po nulini demeni, o antroje dar ir pakeite k-1=j, gau-name Sm=(m-1Σk=0)(-1)^k(m–1//k)f((x+1)+(m-1)-k)-(m-1Σj=0)(-1)^j(m–1//j-1)f(x+(m-1)-j)=Δ^(m-1)f(x + 1) – Δ^(m-1)f(x) = Δ^(m-1)(f(x + 1) – f(x)). <|

Isvada. Jei n,m >=0, tai (Δ^m)(x^n)=(mΣk=0)(-1)^k(m//k)(x + m – k)^n;

(Δ^m)(0^n) := Δ^m)(x^n)|x=0 =(mΣk=0)(-1)^k(m//k)^n

Dydziai (Δ^m)(0^n), m,n>=0, vadinami Morgano skaiciais. Jei m<=n – tai n aibes siurjekciju I m aibe skaicius, ir jei m > n, tai bet kokiam x € R, (Δ^m)(x^n)=0. Is tiesu, kiekvienas operatoriaus Δ pritaikymas sumazina polinomo x^n laipsni vienetu.

Kai x = 0, is cia isplaukia tapatybe

(Δ^m)(0^n) =(mΣk=0)(-1)^k(m//k)(m-k)^n=0, m>n.

Kadangi atveju m > n ir siurjekciju skaicius lygus nuliui, tai darome isvada, kad Morgano skaiciai visada isreiskia siurjekciju kieki.

11. Laipsnine generuojanti funkcija

Formali laipsnine eilute a0+a1x+a2x^2+•••+anx^n+. vadinama sekos generuojancia funkcija (l.g.f.).

1 teorema (Vandermondo sasuka). Bet kuriems naturaliesiems skaiciams k ir m, k,m < n, teisinga lygybe (n//k)=(kΣj=0)(m//j)*(n – m//k – j) |> Panaudoje laipsniniu eiluciu (siuo atveju, polinomu) dauginimo taisykle, gauname (1+x)^n = (1+x)^(n-m)(1+x)^m =(Xi>=0 )(n – m//i)x^i(Σj>=0)(m//j)x^i=

=(Xk>=0)((Xi,j>=0,i+j=k(n-m//i)(m//j))x^m. Sulygine koeficientus prie xx^k, baigiame teoremos irodyma <|

2 teorema. Su bet kokiu n >= 0 teisinga lygybe (nΣk=0)((-1)^k+1/k + 1)(n//k)= – 1/n+1

Apibendrintoji Niutono binomo formule (1=x)^u=(ooΣk=0)(u//n)x^n, x,u $ R, |x|<1

12. Katalano skaiciai

1 teorema. Yra Cn =(1/n)(2n – 2//n – 1) n>=2 demenu suskliaudimo budu. Skaiciai Cn vadinami Katalano vardu.

13. Eksponentines generuojancios funkcijos Sekos {an}, n>= 0 eksponentine generuojancia funkcija (e.g.f.) vadinama formali eilute f(x) := a0 + a1x/1!+ a2x^2/2!+.+anx^n/n!+ . . . .

Lema. Jei f(x) – sekos {an} e.g.f., tai f0(x) – sekos {{an+1}, n>=0 e.g.f.. Formali suma f(x) + g(x) atlikta panariui yra sekos {an + bn}, n >=0 e.g.f., o sandauga f(x)g(x)– sekos cn :=(nΣk=0)(n//k)akb(n-k) e.g.f.

Isvada. Belo skaiciu sekos {Bn}, n >=1, e.g.f. lygi B(x) := exp{e^x – 1}. |> Is rrekurenciosios formulas Bn+1 =(nΣk=0)(n//k)Bk ir is Lemos isplaukia sarysis B0(x) = e^xB(x). Sios diferencialines lygties sprendinys su salyga ir yra isvados funkcija.

2 teorema. Tegu s(n, k) – pirmos rusies Stirlingo skaiciai. Sekos {s(n, k)}, n>=k e.g.f. lygi

fk(x) :=(Xn>=k)s(n, k)*(x^n/n!)=(1/k!)(log(1 + x))^k, |x| < 1, k>=0.

14. Rekurentieji sarysiai

Nagrinesime sekas, kuriu n-tasis narys tam tikra formule yra isreiskiamas per jos narius su mazesniais indeksais. Be to, vienetinumui uztikrinti nurodoma pirmuju sekos nariu. Tokios israiskos vadinamos rekurenciosiomis formulemis.

15. Rekurentieji sarysiai. Bendra teorija

Tarkime, kad seka {un}, n>= 0 yra apibrezta r eiles sarysiu un+r + a1un+r-1 + • • • + arun = 0, n>=0, ir pradiniais nariais u0, u1, . . . , ur-1. Sio pavidalo formules vadiname tiesiniais homogeniniais rekurenciaisiais sarysiais, oo polinomas A(x) =(rΣj=0)ajx^j , a0 := 1vadinamas charakteristiniu polinomu.

1 teorema. Sandauga A(x)U(x) yra polinomas D(x) :=(r-1Σk=0)dkx^k su dk =(kΣj=0)aju(k-j), 0<=k<=r – 1. |> Daugindami A(x) ir U(x) panariui, gauname laipsnine eilute su koeficientais dk =(kΣj=0)aju(k-j). Cia laikome, kad aj = 0 , kai j>= r + 1. Jei k <=r – 1, formule yra ieskomoji. Imkime paeiliui k = r, r+ 1, . . . ir naudodami un+r + a1un+r-1 + • • • + arun = 0, isitikinkime, kkad tada dk=0.

Isvada. Generuojanti funkcija U(x) = D(x)/A(x) yra racionalioji funkcija.

Toliau funkcijai U(x) taikysime racionaliuju funkciju teorija. Tokiu funkciju kune C(x) egzistuoja U(x) israiska paprasciausiuju trupmenu suma (*) U(x)=(kΣi=1)(riΣj=1)(lij/(1 – λix)^j). Cia λi-1 $ C, 1<=i<=k – charakteristinio polinomo A(x) saknys, rr – ju kartotinumai, r1 + • • • + rk = r, o lij $ C.

2 teorema. Jei U(x) turi (*) israiska tai un=(kΣi=1)* *( λ(n//i)(riΣj=1)lij(j + n – 1//n). n>=0. |> Pagal apibendrintaja Niutono binomo formule 1/(1 – λ ix)^j =(ooXn=0)(-j//n)(-1)^n λn//i x^n = (ooΣn=0)(n+j-1//n) λ n//I^n, | λ ix| < 1. Istate I (*) formule ir sulygine koeficientus prie vienodu x laipsniu, baigiame 2 teoremos irodyma <|

Isvada. Tarkime, kad seka {un}, n _ 0, apibrezta sarysiu un+2 +a1un+1 +a2un = 0 ir pradinemis salygomis u0 = u1 = 1. Jei A(x) = a2(x – x1)(x – x2), x1<>x2, λ i = x1-1, tai un = c1 λ n//1 + c2 λ n//2 o konstantos c1, c2 randamos is pradiniu salygu. Jei A(x) = a2(x – x1)2, λ = x1-1, tai un = c1 λ^n + c2n λ^n, o konstantos c1, c2 randamos is pradiniu salygu.

16. Sudetiniu funkciju Tayloro koeficientu rekurentieji sarysiai

1 teorema. Funkcijos F(x) Tayloro koeficientai bbn tenkina rekurentuji sarysi

bn+1 =1/(n + 1)(nΣj=0)a(n-j+1)bj , b0 := 1, n>=0.|> Diferencijuodami gauname F’(x) =(ooXn=1)nbnx^(n-1) = =F(x)(1Xl=0)a(l+1)x^l =(1Xn=0)(( nΣj=0)bja(n-j+1))x^n. Kadangi funkcijos, esancios kaireje sios lygybes puseje, koeficientas prie x^n lygus (n+1)bn+1, apskliaustoji suma yra jo israiska. <|

2 teorema. Funkcijos Gm(x) := (A(x))^m :=((ooXk=0)akx^k)^m, m $ N, a0 <> 0 su apreztais realiais aj Tayloro koeficientai gn := gn(m) tenkina rekurentuji sarysi gn+1 = a0-1(nΣj=0)(m – (m + 1)j/(n + 1))a(n-j+1)gj , g0 = am//0 , n>=0.

17. Grandinines trupmenos

Reiskini α = q0 +(1/(q1 + (1/(q2+. (1/(qk-1+ 1/qk))))))) vadiname grandinine trupmena. Trumpesnis zymuo: α = [q0, q1, q2, . . . , qk]. Cia q0 $ Z, qj $ N, 1<= j<= k, o k>= 0 – sveikasis skaicius.

1 teorema. Kiekviena racionaluji skaiciu galime isreiksti grandinine trupmena, be to, vieninteliu budu.

2 teorema. Pazymekime P-1 = 1 ir Q-1 = 0. Artiniu skaitikliai ir vardikliai tenkina siuos rekurenciuosius sarysius: Pk = qkPk-1 + Pk-2 , Qk = qkQk-1 + Qk-2 , k>=1.

Isvada. Seka Qk, k >=0, grieztai monotoniskai dideja.

3 teorema. Kai k>=1, tai det(Pk , Pk-1//Qk, Qk-1)= PkQk-1 – Pk-1Qk = (-1)^(k+1). Be to, δk – δk-1 =(-1)^(k+1)/(QkQk-1) |> Skaiciuodami determinanta pritaikome 2 teorema. Jis lygus priesingam determinantui, kuriame elementu indeksai vienetu yyra mazesni. Po k zingsniu gauname jo reiksme:

(-1)^k(P0Q-1 – P-1Q0) = (-1)^k(q0•0-1•1)=(-1)^(k+1). Isvedant antraja formule, pakanka subendravardiklinti ir pritaikyti ka tik gauta lygybe. <|

Isvada. Teisingos nelygybes δ0 < δ1 < • • •

2. Miskas ir medziai

Grafas, neturintis ciklu(beciklis), vadinamas misku, o jungusis miskas – medziu.

1 teorema. Grafas yra miskas tada ir tik tada, kada bet kokia virsuniu pora jungia ne daugiau kaip vienas takas.

Irodymas. Jei grafas nera miskas, jame egzistuoja ciklas x0x1.xlx0. Todel turime du

takus x0x1.xl ir x0xl. Atvirksciai, tarkime, kad P = x0.xl ir P‘ = x0yl.ys = xl – du takai, jungiantys x0

su xl. Tarkime, kad i+1 – maˇziausias indeksas, su kuriuo xi+1 ≠ yi+1, o j≥i maziausias indeksas su kuriuo yj+1 jau priklauso P, t.y. yj+1 = xk. Tada xi.xkyj .yi+1 yra ciklas. Todel grafas nera miskas.

2 teorema. Sie tvirtinimai yra ekvivalentus:a) G yra medis; b) G yra minimalus jungus grafas, t.y. bet kurios briaunos atemimas is grafo padidintu komponenciu skaiciu; c) G yra maksimalus beciklis grafas, t.y. sujungiant bet kokias neincidencias virsunes butu sukuriamas ciklas.

Irodymas. Pazymekime V,E grafo G virsuniu ir briaunu aibes, xy e E – bet kokia jo briauna, o u, v – bet kokias dvi neincidencias virsunes. Jei G – medis ir grafas G − xy butu jungus, tai G turetu du takus P = xx1.xky ir P = xy, vadinasi, todel turetu cikla P = xx1.xkyx. Tad, is a) isplaukia b). Briauna, kurios atemimas didina grafo komponenciu skaiciu vadinama tiltu. Jei G – medis, tai jame egzistuoja takas nuo u iki v. Isvestas naujasis takas uv su senuoju sudarytu cikla, ir grafas G + uv jau turetu cikla. Tad, is a) isplaukia c)Tarkime, G – minimalus jungus grafas. Jei G nebutu medis, o turetu cikla xx1.yx,

tai ismetus briauna xy, jo jungumas nepakistu. Priestara irodo, jog is b) isplaukia a).

Isvada. Jungiame grafe egzistuoja medis, kurio virsuniu aibe sutampa su visa grafo virsuniu aibe.

Isvadoje gautasis medis vadinams minimaliu jungianciuoju medziu (karkasu).

Karkasinio medzio isvedimo budai

1 budas. Jungiame grafe G = (V,E) fiksuokime virsune x e V ir virsuniu aibe suskaidykime i nepersikertancias aibes Vi = {y e V : d(x, y) = i}, i = 0, 1, . . . , s < oo. Jei yi 2 Vi , tai egzistuoja x−yi takas xz1.zi−1yi. Pastebekime, kad Vj ≠ (tuscia aibe), j = 0, 1, ., i, kai i > 0. Taigi, bet kuriam yi e Vi rasime y‘i−1 e Vi−1. Is, gal but, keliu galimybiu pasirinkime viena. Kai y perbegs V , priskirtieji y‘ (artimesni pradiniam taskui) ir y sudarys junguji grafa T = (V,E‘), E‘ = {yy‘ : y e V, y ≠ x}. Kadangi i y patenkama tik is vieno tasko, jis neturi ciklu. Taigi, T – karkasinis medis.

2 (indukcinis) budas. Imkime x e V . Tada T1 := ({x}, (tuscia aibe)) – medis. Tarkime, kad jau

sukonstravome medziu seka T1C T2 C • • • C Tk C G ir medzio Ti eile yra i. Jei k < n = |V |, tai egzistuoja pora (y, z) tokia, kad z e V (Tk), y e V V (Tk), cia V (Tk) – Tk virsuniu aibe, ir zy e E. Priesingas atvejis priestarautu grafo G jungumui. Apibrezkime Tk+1 = (V (Tk) U {y},E(Tk) U {zy}). Baigtiniame grafe sis procesas baigtinis. Jis baigiasi, kai k = n. Medi galime charakterizuoti ir pagal jo skaitinius parametrus: eile ir didumu.

3. Viena optimizavimo problema

Uzdavinys Reikia suprojektuoti pigiausia vandentiekio tinkla, jungianti visas miestelio sodybas, kada zinomos visu trasu tarp namu kainos. Jeigu gamtines kliutys yra neiveikiamos, galima laikyti, kad trasos per sia kliuti kaina yra begaline. Formalizuojant galima isivaizduoti, kad turime pilnaji n grafa G = (V,E) ir apibrezta funkcija f : E -> R^+.

Reikia isvesti karkasini medi (vesti kelias linijas i ta pacia sodyba visada bus brangiau) T = (V,E‘) toki, kad bendra kaina F(T) = (∑ xy2E0 ) (xy) butu maziausia. Si medi vadinkime ekonomisku. Uzdavinio sprendimo algoritmai

1 algoritmas:

a) imame briauna e = xy e E su maziausia kaina, f(e) = min(xy e E)f(xy); b) is likusiu briaunu isrenkame pigiausia; c) procesa kartojame su salyga, kad isrenkamos briaunos nesudarytu ciklo. Procesas baigtinis, o gautasis grafas, kaip maksimalus beciklis grafas, pagal 2.2 teoremos c) punkta bus karkasinis medis. Gautojo medzio ekonomiskuma isnagrinesime veliau.

2 algoritmas:

a) imame briauna e = xy e E su didziausia kaina, f(e) = max(xy2E)f(xy) ir ja atimame is grafo G; b) ta pati kartojame su grafu G − e; c) procesa baigiame, kai kitas briaunos atemimas padidintu grafo jungumo klasiu skaiciu.Gautasis grafas, kaip minimalus jungus grafas, pagal 2.2 teoremos b) punkta bus karkasinis medis.

3 algoritmas:

a) imame bet kokia virsune x1 e V ; b) imame viena is pigiausiu incidenciu x1 briauna‘ x1x2 e E, x2 e V {x1}; c) rade x1, . . . , xk ir briaunas xixj , i < j≤k ieskome x = xk+1 e V {x1, . . . , xk}, tokios, kad kaina f(xk+1xi) su kazkokiu i ≤ k butu minimali. Procesas baigiasi, kai k = n, o briaunu skaicius lygus n − 1. Taip gavome karkasini medi.

1 teorema. Virsuje aprasytieji algoritmai duoda ekonomiskus medzius. Jei kainos

funkcija yra injektyvi, tai ekonomiskasis medis yra vienintelis.

Irodymas. Tarkime, jog T – ekonomiskas medis, turintis maksimalu skaiciu bendru briaunu su T1, medziu, gautu naudojant 1 algoritma. Jei E(T) ≠ E(T1), imkime pirma briauna xy is T1, bet nepatekusia i T. Medyje T irgi yra x − y takas, sakykim P, kurio bent viena briauna, tegu uv, nepatenka i T1. Renkant xy, si briauna uv buvo viena is kandidaciu, todel f(xy)≤f(uv). Sudarykime nauja karkasini medi T‘ = T − uv + xy. Jo kaina F(T‘) = F(T) − f(uv) + f(xy) ≤ F(T), todel ir naujasis medis yra ekonomiskas. Bet jis turi dar daugiau bendru briaunu su T1, nei T. Priestara irodo, kad T = T1. 2 bei 3 algoritmais gautu medziu ekonomiskumas irodomas panasiais samprotavimais. Nagrinekime vienati, kai visos briaunu kainos skirtingos. Taikome matematine indukcija grafo eiles atzvilgiu. Kai n = 2, 3, teiginys trivialus. Padare prielaida, jog teorema teisinga visiems n ≥ 4 eiles grafams, nagrinedami (n + 1) eiles pilnaji grafa, skelkime virsuniu aibe i dvi dalis V = V1 ∩ V2, su n1, n2 ≥ 2 virsuniu, n1 + n2 = n + 1 ir nagrinekime indukuotosius pografius. Juose egzistuoja vieninteliai ekonomiski karkasiniai medziai T1, T2. Raskime min (x2V1/y2V2) f(xy).Tarkime, si minimali kaina igyjama briaunoje xy, jungiancioje abu pografius. Isitikinkime,kad medis T4 := T1 U T2 + xy yra ekonomiskas. Tarkime, T – ekonomiskas medis. Jei T4 ≠T, tai vienintele briauna is T4, nepatekusi i T, gali buti tik xy. Medyje T turi buti kita briauna uv, jungianti T1 su T2. Bet tada f(xy) < f(uv) ir medzio T − uv + xy kaina butu grieztai mazesne, nei T. Priestara irodo ekonomisko medzio vienati.

Pastaba. Vienaties irodymas duoda dar viena karkasinio medzio konstravimo buda: kai briaunu kainos skirtingos, galima grafa skaidyti i mazesnius ir juose ieskoti karkasiniu medziu, o veliau juos sujungti.

4. Grafo parametru rysiai

1 (Euler’io) lema. Grafo virsuniu laipsniu suma yra lyginis skaicius.

Irodymas. Pakanka pastebeti, jog kiekviena briauna, turedama du galus, inesa 2 vienetus i suma (1) (∑x2V)δ(G) = 2|E|

1 isvada. Nelyginio laipsnio virsuniu kiekis grafe yra lyginis skaicius.

2 isvada. Tarkime d(G) = 1/(|V |) (∑x2V)δ(x) − − vidutinis grafo laipsnis, o ε = |E|/|V | – vidutinis briaunu skaicius, tenkantis vienai virsunei. Tada ε (G) = d(G)/2.

Irodymas. (1) suma lygi |V |d(G). Lema islieka teisinga ir bendresniems grafams.

2 lema. Tarkime, kad G‘ = (V‘,E‘) ir G“ = (V“,E‘), V‘ V“ = (tuscia aibe), – du pilnieji grafai su |V‘| = n1, |V“| = n2, n1 + n2 = n. Grafo G‘U G“ didumas didziausias, kai n1 = n − 1, o n2 = 1.

Irodymas. Dabar grafe G‘UG“ turime (n1(n1 − 1))/2 + (n2(n2 − 1))/2 briaunu. Apskaiciuokime, kaip keiciasi bendras briaunu skaicius, jei viena virsune didesni grafa padidintume, o kita, mazesniji, – sumazintume. Tegu n1≥n2. Gautasis briaunu skaicius butu lygus (n1(n1 + 1))/2 + ((n2 − 1)(n2 − 2))/2, o skirtumas – n1 + 1 − n2 ≥ 1.Taigi, kartojant panasia procedura pasieksime maksimalu bendra briaunu skaiciu, kai n1 =n − 1, n2 = 1.

1 teorema. Jei n – grafo eile, m – didumas, o k – jo komponenciu kiekis, tai (1.1) n − k ≤ m ≤1/2 (n − k)(n − k + 1).

Irodymas. Pirmaja nelygybe irodysime, taikydami matematine indukcija m ≥ 0 atzvilgiu. Kai m = 0, turime nulini grafa su n jungumo klasiu. Tad, nelygybe triviali. Tegu m1 < m2 < • • • – n eiles grafu G, turinciu k jungumo klasiu, didumai su savybe: ismetus dar viena briauna is G, padidetu jo jungiu komponenciu skaicius. Kai mj−1 ≤ m < mj , kairioji is (1.1) nelygybiu isplauks is nelygybes, kai m = mj−1. Todel pakanka nelygybe irodyti tik siai sekai. Tarkime, jog nelygybe irodyta grafui su mj−1 briauna, ir nagrinekime atveji |E| = mj . Kadangi dabar kiekviena briauna yra tiltas, ismetus kazkuria is ju gauname grafa, kuriam galioja indukcijos prielaida. Tegu tai – grafas G‘ = (V‘,E‘), |V‘| = n, |E‘| = mj − 1.Jis turi k + 1 klase, todel n − (k + 1) ≤ mj − 1. Is cia isplaukia pirmoji is (1.1) nelygybiu. Vertindami m is virsaus, nagrinekime pati ”blogiausia” atveji, kai kiekviena is jungumo klasiu yra pilnieji pografiai. Pritaike lema kiekvienai siu klasiu porai, gauname, kad bendras briaunu kiekis m bus maksimalus, kai viena is ju yra labai didele, o likusios – tusti grafai. Todel tada n-os eiles grafe su k jungumo klasiu, pografiu eiles yra n − k + 1, , 1, . . . , 1. Taigi, maksimalus briaunu skaicius lygus

((n − k + 1)(n − k))/2

Isvada. Jei n eiles grafas turi daugiau nei 1/2 (n−1)(n−2) briaunu, tai jis yra jungusis.

2 teorema. n-os eiles jungusis grafas yra medis tada ir tik tada, kada jo didumas lygus n − 1.

Irodymas. Pagal kairiaja (1.1) nelygybe jungiajame n eiles grafe yra ne maziau, negu n − 1 briauna. Jeigu ju butu daugiau, grafas turetu tureti cikla . Taigi, teoremos salyga yra butina. Jos pakankamumas akivaizdus.

1 isvada. n-os eiles grafo jungianciojo medzio didumas lygus n − 1.

2 isvada. n-os eiles misko is k medziu didumas lygus n − k.

5. Grafo planarumas

Vaizduojant grafus plokstumoje ir breziant briaunas apsiribojama Zordano kreivemis. Grafus, kuriuos galima pavaizduoti plokstumoje, taip, kad skirtingos briaunos neliestu viena kitos ne virsuniu taskuose, vadiname planariaisiais. Pati plokstumoje isvesta grafa vadiname ploksciuoju grafu.

Plokstumos sritys, apribotos plokscio grafo briaunomis ir virsunemis, vadinamos grafo veidais. Visi plokstieji grafai turi viena begalini veida. Ploksciasis grafas kartu su savo veidais vadinamas zemelapiu. Tada veidus geriau vadinti valstybemis.

1 teorema (L.Euler, 1752). Jei G – jungus zemelapis, n – jo eile, m – didumas ir f – valstybiu skaicius, tai n-m+f=2. |> Indukcija f atzvilgiu. Jei f = 1, tai grafas neturi ciklu. Vadinasi, jis yra medis. Todel musu teiginys isplaukia is 3.2 teoremos isvados. Tariame, kad teorema irodyta del zemelapiu su mazesniu uz f > 1 skaiciumi valstybiu. Pastebekime, jog grafas turi ciklu. Imkime bet kuria ciklo briauna ir atimkime is grafo. Dvi valstybes, kurios buvo atskirtos ciklo, susijungia i viena. Todel naujasis zemelapis tures viena valstybe maziau. Jam pritaikome indukcine prielaida. <|

2 teorema. Planarusis n>=3 eiles jungus grafas turi m<=3n – 6 briaunu. Jei toks grafas turi maziausio ilgio 3<=g Taikome matematine indukcija grafo eiles n atzvilgiu. Maziems n teiginys patikrinams betarpiskai. Tarkime, kad teorema irodyta visiems n – 1 eiles grafams, ir ju virsuniu spalvinimui panaudota ne daugiau Δ(G) + 1 spalvu. Is n eiles grafo atimkime viena virsune v ir pasinaudokime indukcijos prielaida. Nudaze grafa G-v, griztame prie G. Virsunes, gretimos v, yra nudazytos ne daugiau kaip Δ(G) + 1 spalvu. Ju yra ne daugiau kaip Δ(G). Vadinasi, viena spalva yra nepanaudota. Ja nudaze v, baigiame teoremos irodyma.<|

Lema. Kiekvienas planarus grafas turi ne didesnio kaip penktojo laipsnio virsune. |> Galime nagrineti tik jungius planarius n>=3 eiles grafus. Jei δ(v)>=6 kiekvienai virsunei v$V , tai is lygybes (Σv$V)δ(v)=2m, cia m – grafo didumas, isplaukia 6n<=2m. Tai priestarauja 5.2 teoremos isvadai, teigianciai, kad planariajam jungiam grafui m<=3n-6, kai n>=3. <|

2 teorema. Kiekvienas planarusis grafas yra penkiaspalvis. |> irodyme remsimes indukcijos principu. Kai n<=5, teiginys trivialus. Tarkime, kad ji jau irodem kievienam planariajam grafui, kurio eile mazesne uz n. Pagal lema galime isskirti virsune v su δ(v)<=5. Jei δ(v) < 5, Grafui G-v pritaikome indukcijos prielaida ir nudazome jo virsunes, panaudodami 5 spalvas. Virsunei v gretimos virsunes nuspalvinamos maziau nei 5 spalvomis. Sutaupytaja spalva nudazome v ir taip baigiame uzduoti. Tegu δ(v)=5. Nagrinekime v gretimasias virsunes v1, v2, v3, v4, v5. Bent dvi is ju yra negretimos tarpusavyje. Tegu v1 ir v2 negretimos virsunes. Nagrinekime sutrauktaji grafa G’=G{vv1, v2}. Pagal indukcijos prilaida jam nuspalvinti pakako i spalvu. Taip ir nudazykime G’. Dabar isplete G’ iki G, matome, kad gretimosios v virsunes sutaupo viena spalva, kuria galime nuspalvinti pacia v.

Isvada. Kiekvienas zemelapis yra penkiaspalvis.

3 teorema. Kiekvienas zemelapis yra keturspalvis.

7. Medziu skaicius

Grafa su sunumeruota virsuniu aibe vadinsime numeruotoju grafu.

1 ( Cayley’io) teorema. Is viso galime sudaryti n^(n-2) neizomorfisku numeruotu n eiles medziu. |> (Prufer’io) Tarkime G – nagrinejamu medziu aibe. Kadangi seku aibes {(a1,.,an-2):1<=ai<=n, 1<=i<=n – 2}=:A galia yra n^(n-2), pakaks rasti bijektyvu atvaizdi A –> G. Kai n<=2, teiginys akivaizdus. Tegu toliau n > 2. Medziui G=(V,E), kurios virsuniu aibe sunumeruota, V={x1,.,xn}, vienareiksmiskai priskirsime seka α=(a1,.,an-2)$A, vadinama medzio Prufer’io kodu. Pradekime nuo medzio galines virsunes, kurios laipsnis lygus 1. Tokios virsunes egzistuoja, nes kiekviena briauna turi dvi virsunes ir todel (n Σi=1) δ (xi) = 2(n – 1). Is keliu tokiu virsuniu isrinkime ta, kurios indeksas yra maziausias. Tegu tai virsune xb1 , o a1 – indeksas virsunes, gretimos pirmajai. Grafas G-xb1 yra n-1 eiles medis, todel procesa galima kartoti, kol virsuniu, likusiu grafe, skaicius yra didesnis uz 2. Kai sis skaicius lygus 2, mes jau esame sudare vienintele seka (a1,.,an-2). <|

Pora (G,G’) pavadinkime junginiu.

Isvada. Yra n^(n-1) sakniniu n eiles medziu.

Binareisiais medziais vadiname medzius, kurie turi viena 2-ojo laipsnio virsune, vadinama saknimi, o kitu virsuniu laipsniai yra 3 (jos vadinamos vidinemis virsunemis) arba 1 (sios virsunes vadinamos lapais). Binarusis medis turi tureti n! lapu.

2 teorema. Teisingas rekurentusis sarysis CN =(N-1 Σk=1)CkCN-k, C1 = 1. Be to, CN =1/N((2N-2)//(N-1)).

8. Grafu teorijos ir algebros sarysiai

Kvadratine matrica A=((aij )), 1<=i, j<=n, vadiname multigrafo gretimumo matrica.

Matrica BG=B=(bij), 1<=i<=n, 1<=j<=m, vadiname multigrafo (grafo) incidentumo matrica, jei bij =1, jei i virsune yra incidenti j briaunai, kuri nera kilpa, bij=2, jei i virsune yra incidenti j briaunai, kuri yra kilpa, bij=0, jei i virsune nera incidenti j briaunai.

1 teorema. Tarkime G – numeruotas multidigrafas be kilpu, A ir B – jo gretimumo ir incidentumo matricos atitinkamai. Tada BB’=D-A. Cia ’ zymi matricos transponavima, o D –diagonali matrica, kurios istrizaineje yra is eiles surasyti virsuniu laipsniai. |> Jei cij – matricos BB’ bendrasis narys, tai cij=(mΣl=1)bilbjl. Todel, kai i <> j, sandauga bilbjl lygi 0 arba -1. Pastaroji lygybe yra teisinga tik tuo atveju, kai xixj = el. Sudedant pagal l, -1 dauginsis is tokio kaiciaus, kiek yra briaunu, jungianciu xi ir xj. Kai i = j, cii yra matricos istrizaines narys. Matrica A turi nuline istrizaine. Cij suma lygi briaunu, isvestu is xi skaiciui. <|

Standartine baze bus funkciju rinkinys f1,.,fn, kai funkcija fj apibreziama lygybemis fj(xi)=δij. Cia δij – Kronekerio simbolis. Kai L perbegs visus grafo ciklus, gausime aibe funkciju {gL}, ju tiesinis apvalkas Z(G) erdveje F1(G) vadinamas ciklu poerdviu. Jo dimensija dimZ(G) vadinama grafo G ciklomaciuoju skaiciumi.

2 teorema. Briaunu funkciju erdve – tiesiogine tarpysavyje ortogonaliu poerdviu Z(G) ir U(G) suma. Jei grafas G turi n virsuniu, m briaunu ir k jungumo klasiu, tai dimZ(G)=m-n+k, dimU(G)=n-k.

Kirchhoff’o potencialu desnis. Jei C fundamentaliuju ciklo vektoriu sudaryta matrica, o ¯p – potencialu skirtumu vektorius stulpelis, tai C¯p = 0.