Kombinatoriikka [lecture notes] [PDF]

Zitiervorschau

Kombinatoriikka Vesa Halava

Luentomoniste

Turun yliopisto Matematiikan laitos 20014 Turku

2004

Sisältö

2

Sisältö 1

BINOMIKERROIN

1.1 1.2 1.3 1.4 1.5 1.6 1.7

Joukoista . . . . . . . . . . . . . . . Permutaatiot ja kombinaatiot . . . . Toistokombinaatiot ja -permutaatiot Multinomiluku . . . . . . . . . . . . Binomikerroin kaavoja . . . . . . . . Sovellus: TN-laskenta . . . . . . . . . Sovellus: Virheitä korjaavat koodit .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

Lokeroperiaate . . . . . . . . . . . . . . . . . . Sovellus: Kasvavat ja vähenevät osajonot . . . . Kaksoislaskenta . . . . . . . . . . . . . . . . . . Sovellus: Jakajien lukumäärän keskiarvo . . . . Seulaperiaate . . . . . . . . . . . . . . . . . . . Sovellus: Derangement-ongelma . . . . . . . . . Sovellus: Eulerin funktio ja Möbiuksen funktio . Sovellus: Primitiiviset sanat . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

Palautuskaava . . . . . . . . . . . . . . . . . . . . . . . Homogeenisen lineaarisen palautuskaavan ratkaisu . . Epähomogeenisen lineaarisen palautuskaavan ratkaisu Matriisit ja rekursiot . . . . . . . . . . . . . . . . . . . Sovellus: Solubiologiasta . . . . . . . . . . . . . . . . . Sovellus: Skolemin ongelma . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

2

PERUSMENETELMIÄ

3

REKURSIOT

4

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8

3.1 3.2 3.3 3.4 3.5 3.6

GENEROIVAT FUNKTIOT

4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8

Jono ja generoiva funktio . . . . . . Tulo- ja summaperiaate . . . . . . . Teoriaa . . . . . . . . . . . . . . . . Laskusäännöt . . . . . . . . . . . . . Rekursiot ja generoivat funktiot . . . Sovellus: Catalanin luvut . . . . . . . Eksponentiaalinen generoiva funktio Sovellus: Derangement-ongelma . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

4

4 5 6 7 8 11 12

17

17 18 18 19 20 22 23 25

28

28 28 33 35 38 38

40

40 41 44 46 49 52 54 55

Sisältö

3

Johdanto Kombinatoriikan kysymykset voidaan jakaa karkeasti kahteen: 1) onko olemassa tietyt ominaisuuden omaavia kombinaatioita, 2) kuinka monta tällaista kombinaatiota on olemassa. Käsite "kombinatorinen todistus" on tuttu monilta eri matematiikan aloilta. Tällöin annettu väite osoitetaan oikeaksi käymällä läpi kaikki kombinaatiot, osoittamalla, että joitakin kombinaatioita on/ei ole olemassa tai laskemalla niiden lukumäärä. Tällä kurssilla on tarkoitus käydä läpi kombinatoriikan perusteita. Erityisesti tarkastellaan kombinatorisia laskenta- ja todistusmenetelmiä sekä jonoja ja niiden jäsenten ratkaisemista. Esimerkkejä ja sovelluksia esiintyy monilta matematiikan aloilta. Luentomoniste perustuu seuraaviin lähteisiin: Aigner, M. and Ziegler, G. M.,

1998.

Ja kson, B. W. and Thoro, D.,

Solving, Addison-Wesley, 1990.

Proofs from the Book , Springer,

Applied Combinatori s with Problem

van Lint, J. H. and Wilson, R. M.,

bridge University Press, 1996. Wilf, Herbert S.,

A ourse in ombinatori s, Cam-

generatingfun tionology, A ademi Press, 1994. (http://www. is.upenn.edu/∼wilf/index.html)

4

1 BINOMIKERROIN

1.1

Joukoista

Olkoon A joukko, sen alkioiden lukumäärää merkitään |A|:lla. Jos A = {a1 , a2 , . . . , an }, niin se on ns. äärellinen joukko. Jos A on ääretön joukko, niin joskus merkitään |A| = ∞. Määritelmä 1.1. Olkoot A ja B kaksi joukkoa, määritellään joukkojen

(i) unioni A ∪ B = {a | a ∈ A ∨ a ∈ B}, (ii) leikkaus A ∩ B = {a | a ∈ A ∧ a ∈ B},

/ B} ja (iii) erotus A \ B = {a | a ∈ A ∧ a ∈ (iv) (karteesinen) tulo A × B = {(a, b) | a ∈ A, b ∈ B}. Joukon A(⊆ E) komplementti AC = E \ A, missä E on niin sanottu perusjoukko. Sanotaan, että joukot A ja B ovat erillisiä, jos A ∩ B = ∅. Lemma 1.1. Olkoot A1 , A2 , . . . , An äärellisiä joukkoja.

(i) (Summasääntö) Jos joukot A1 , A2 , . . . , An ovat (parittain) erillisiä, niin n n X [ |Ai |. Ai | = |A1 ∪ A2 ∪ · · · ∪ An | = | i=1

i=1

(ii) (Tulosääntö) |A1 × A2 × · · · × An | =

n Y i=1

|Ai |.

Todistus. Induktiolla, osoitetaan ensin, että |A1 ∪ A2 | = |A1 | + |A2 | ja |A1 × A2 | = |A1 ||A2 |. Huomaa, että kohdassa (i) joukkojen pitää siis olla erillisiä eli ∀i 6= j , Ai ∩ Aj = ∅. Seuraavassa luvussa tarkastellaan tapausta, jossa tämä ehto ei välttämättä ole voimassa. Joukon A tuloa A × A itsensä kanssa merkitään myös A2 :lla. Kun sovitaan, että A0 = ∅ ja A1 = A, niin tämä yleistyy k ≥ 0 kertaiselle tulolle Ak , jota kutsutaan joukon A k:neksi potenssiksi.

1.2 Permutaatiot ja kombinaatiot

5

Esimerkki 1.1. Äärellistä symbolijoukkoa X = {a1 , a2 , . . . , an } kutsutaan

aakkostoksi. Aakkoston X sana on jono X :n symboleja, esimerkiksi a2 a6 a1 a2 . Sanan pituus on siinä esiintyvien symbolien lukumäärä. Tulosäännön nojalla k-pituisia aakkoston X sanoja on |X|k . Esimerkki 1.2. Kirjastossa on 5 espanjan, 6 tanskan ja 7 englannin kielistä

kirjaa. Kuinka monella tavalla voidaan valita kaksi eri kielistä kirjaa? 1.2

Permutaatiot ja kombinaatiot

Määritelmä 1.2. Kuvaus α : X → X on joukon X = {a1 , a2 , . . . , an } per-

mutaatio, jos se on bijektio. Kaikki n alkioisen joukon permutaatiot muodostavat ryhmän, ns. symmetrisen ryhmän Sn . tä

Permutaatioita merkitään monella eri tapaa. Esimerkiksi voidaan merki  1 2 ··· n α= , i1 i2 · · · in

missä α(aj ) = aij kaikilla 1 ≤ j ≤ n. Seuraavassa esimerkissä esitellään myös ns. syklimerkintä Esimerkki 1.3.  Olkoon X = {1, 2, · · · , 4} ja tarkastellaan permutaatiota 

1 2 3 4 . Permutaation α voidaan kirjoittaa myös muotoon α = 2 1 3 4 (12)(3)(4)(= (12)). Permutaatiot voidaan ajatella n:n alkion järjestyksinä. Helposti huomataan, että n-alkioisella joukolla on n(n − 1) · · · 1 = n! permutaatiota, ts. |Sn | = n! α=

Seuraavaksi tarkastellaan tapauksia, missä n-alkioisesta joukosta valitaan k alkiota. Määritelmä 1.3. Olkoon A n-alkioinen joukko. A:n k alkioista osajoukkoa kutsutaan A:n k-kombinaatioksi. Merkitään n-alkioisen joukon k-kombinaatioiden lukumäärää C(n, k):lla. A:n k eri alkioista jonoa kutsutaan A:n k-permutaatioksi. Merkitään nalkioisen joukon k-permutaatioden lukumäärää P (n, k):lla. Huomautus 1. k -kombinaatiossa alkioden keskinäisellä järjestyksellä ei ole väliä, kun taas k-permutaatiossa on. Huomaa myös, että toistoja ei sallita, jokainen alkio esiintyy siis korkeintaan kerran.   n n! n! (= ). Lause 1.1. P (n, k) = ja C(n, k) = k (n − k)! (n − k)!k!

1.3 Toistokombinaatiot ja -permutaatiot

6

Todistus. Olkoon A = {a1 , a2 , . . . , an }. Tarkastellaan ensin k-permutaatioiden määrää. Kun valitaan k-permutaatiota, niin voidaan ajatella, että 1. paikalle on n vaihtoehtoa, 2:lle (n − 1) jne. k:nelle (n − k + 1). Toisin sanoen P (n, k) = n(n − 1)(n − 2) · · · (n − k + 1) =

n! . (n − k)!

Jokaisen k-permutaation alkiot voidaan järjestää k! tavalla, joten

C(n, k) =

P (n, k) n! = . k! (n − k)!k!

  n n! = Merkitään siis lukua , missä n ∈ N ja 0 ≤ k ≤ n (lue (n − k)!k! k n yli k:n). Näitä lukuja kutsutaan yleisestibinomikertoimiksi .  n Jos k < 0 tai k > n, niin määritellään = 0. k Koska k:n alkion valinta vastaa n − k valitsematta jättämistä, saadaan     n n Seuraus 1.1. C(n, k) = = = C(n, n − k). k n−k Esimerkki 1.4. |Sn | = P (n, n) = n!. Esimerkki 1.5. Kymmenen joukkueen yksinkertaisessa sarjassa (kaikki pe-

laavat kaikkia vastaan kerran) on C(10, 2) =

10! = 45 ottelua. 8!2!

Esimerkki 1.6. 10 kirjaimen aakkostosta muodostetaan 8 kirjaimisia sano-

ja, joissa kukin kirjain saa esiintyä vain kerran. Tällaisia sanoja on P (10, 8).

Esimerkki 1.7. Yhdistyksessä on n tyttöä ja m poikaa. Kuinka monta sel-

laista johtokuntaa, jossa on k tyttöä ja ℓ poikaa, voidaan muodostaa?

1.3

Toistokombinaatiot ja -permutaatiot

Edellisen pykälän kombinaatioissa ja permutaatioissa ei sallittu toistoa. Tarkastellaan seuraavaksi tapauksia, joissa toistot sallittaan. Joukko on ns. toistojoukko, jos samat alkiot voivat esiintyä moneen kertaan. Esimerkiksi {1, 1, 2, 4, 3, 2} on toistojoukko. Määritelmä 1.4. Olkoon A n-alkioinen joukko. Toistojoukkoa B sanotaan

A:n k-toistokombinaatioksi, jos |B| = k ja jokainen B :n alkio on A:n alkio. Merkitään n-alkioisen joukon k-toistokombinaatioiden määrää CT (n, k):lla. Jonoa, jossa on k kappaletta A:n alkioita kutsutaan A:n k-toistopermutaatioksi. Käytetään n-alkioisen joukon k-toistopermutaatioden lukumäärälle merkintää PT (n, k).

1.4 Multinomiluku

Lause 1.2. PT (n, k) = n ja CT (n, k) = k



7

 n+k−1 . k

Todistus. Joukon A k-toistopermutaatiot voidaan ajatella joukon Ak alkioina (tai k-pituisina sanoina), joten tulosäännön mukaan PT (n, k) = |Ak | = nk . Olkoon A = {a1 , a2 , . . . , an } ja B A:n k-toistokombinaatio. Joukossa B on x1 kappaletta alkiota a1 , x2 alkiota a2 , jne, xn alkiota an , ja (1)

x1 + x2 + · · · + xn = k.

CT (n, k) on siis yhtälön (1) kokonaislukuratkaisujen lukumäärä, kun oletetaan, että xi ≥ 0 kaikilla 1 ≤ i ≤ n. Tämä lukumäärä taas on ekvivalentti sen kanssa, kuinka monella tavalla k 1:stä voidaan jakaa n lokeroon. Tarkastel· · · 1}, ja lisätään siihen n − 1 erotinta |, esim. 1||1|1|, kun n = 5 laan jonoa 11 | {z k kpl

ja k = 3. Näin k 1:stä on jaettu n lokeroon. Jonossa on nyt n+k−1 paikkaa (k ykköstä, n − 1 pystyviivaa). Siis k-toistokombinaatioiden määrä saadaan kun lasketaan kuinka monella tavalla k ykköstä voidaan sijoittaa n + k − 1 paikkaan (loput paikat täyttyvät pystyviivoilla). k-toistokombinaatioiden määrä on siis  yhtä suuri  kuin n + k − 1-alkioisen joukon k-kombinaatioiden lukun+k−1 . määrä k Esimerkki 1.8. Ed. lauseen todistuksesta saadaan, että yhtälön

x1 + x2 + · · · + xn = k sellaisten kokonaislukuratkaisujen, missä xi ≥ 0, lukumäärä on

Esimerkiksi yhtälöllä

on





 n+k−1 . k

x1 + x2 + x3 + x4 + x5 = 3    5+3−1 7 = = 35 ei-negatiivista kokonaislukuratkaisua. 3 3

Esimerkki 1.9. Mikä on yhtälön x1 + x2 + x3 + x4 = 10 kokonaislukuratkaisujen lukumäärä, kun a) ∀i, xi > 0, b) x1 ≥ 2, x2 ≥ 1, x3 ≥ 4 ja

x4 ≥ 0? 1.4

Multinomiluku

Määritelmä 1.5. Joukon A partitio on sen jako erillisiin epätyhjiin osajouk-

koihin. Siis A1 , A2 , . . . , Ak on joukon A partitio, jos

∀i 6= j : Ai ∩ Aj = ∅

ja

k [

i=1

Ai = A.

1.5 Binomikerroin kaavoja

8



 n Määritelmä 1.6. Multinomiluku eli multinomikerroin ilr1 , r2 , . . . , rm moittaa, kuinka monella eri tavalla n-alkioinen joukko voidaan jakaa m joukon partitioon, jossa joukot ovat r1 -,r2 -,. . . ,rm -alkioiset. Huomaa, että r1 + r2 + · · · + rm = n. Huomautus 2. Partitiossa joukkojen järjestyksellä on väliä. Esimerksi jou-

kolla {1, 2} on kaksi partiota yksi alkioisiksi joukoiksi, nimittäin A1 = {1}, A2 = {2} ja A1 = {2}, A2 = {1}. Huomautus 3. Edellisessä määritelmässä myös tapaus ri = 0 sallitaan.



n r1 , r2 , . . . , rm



n! . r1 !r2 ! · · · rm !   n Todistus. n alkiosta r1 voidaan valita tavalla, n−r1 alkiosta r2 voidaan r 1   n − r1 tavalla jne. Tulosäännön mukaan saadaan, että valita r2        n n n − r1 n − r1 − · · · − rm−1 = ··· r1 , r2 , . . . , rm r1 r2 rm n! . = r1 !r2 ! · · · rm ! Lause 1.3.

=

Esimerkki 1.10. Tarkastellaan aakkostoa {a, b, c}. Kuinka monta sellaista sanaa on olemassa, joissa on 3 a:ta, 2 b:tä ja 4 c:tä? Sanojen pituus on siis 9. Sanan 9 "paikkaa" partitioidaan siis 2, 3 ja 4 alkiosiksi osajoukoiksi, joten sanoja on   9 = 1260. 2, 3, 4 Esimerkki 1.11. Kuinka monella tavalla sanan VAKAVA kirjaimet voidaan

järjestää?

Esimerkki 1.12. Osoita, että

(x1 + x2 + · · · + xm )n = 1.5

X

r1 +r2 +···+rm =n



 n xr1 xr2 · · · xrmm . r1 , r2 , . . . , rm 1 2

Binomikerroin kaavoja

Tässä pykälässä tarkastellaan binomikertoimeen liittyviä kaavoja ja yhtälöitä. Näille kaavoille ja yhtälöille on olemassa monia erilaisia todistuksia.

1.5 Binomikerroin kaavoja

9

Edellä todettiin jo, että

    n n = , k n−k ks. Seuraus 1.1.       n n−1 n−1 . Lause 1.4. = + k k−1 k

Todistus. DEMO.

Lauseen 1.4 mukaan binomikertoimet voidaan järjestää ns. Pas alin kolmioksi.

n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7

1

1

1 7

1 6

1 5 21

1 4 15

1 3 10 35

1 2 6 20

1 3 10 35

1 4 15

1 5 21

1 6

1 7

1

1

          n n+1 n+2 n+k n+k+1 Lause 1.5. + + + ··· + = . 0 1 2 k k   n+k+1 Todistus. Tarkastellaan lukua eli (n + k + 1)-alkioisen joukon k   n+k {1, 2, . . . , n + k + 1} k-kombinaatioita. On olemassa kombinaatioik   n+k−1 kombinaatiota, joihin 1 kuuluu, mutta 2 ta, joihin 1 ei kuulu,   k−1 n+k−2 ei kuulu, kombinaatiota, joihin 1 ja 2 kuuluu, mutta 3 ei kuulu, k−2 jne. Huomautus 4. Edellinen lause voidaan todistaa myös Lauseen 1.4 avulla tai vaikka tarkastelemalla Pas alin kolmiota.       n k n n−r Lause 1.6. = k r r k−r

Todistus. DEMO.            n+m n m n m n m Lause 1.7. = + + ··· + . k 0 k 1 k−1 k 0

1.5 Binomikerroin kaavoja

10

Todistus. Vasen puoli ilmoittaa, kuinka monella tavalla n naisesta   ja m  mien m hestä voidaan valita k-jäseninen joukko. Oikealla puolella keri k−i too kuinka monella tavalla voidaan valita i naista ja k − i miestä.            m n m n m n m+n Lause 1.8. + + ··· + = . 0 0 1 1 n n n   m+n Todistus. Luku kertoo kuinka monella tavalla n naisesta ja m mien hestä voidaan valita n-alkioinen joukko. Oletetaan, että on valittu k miestä, valitaan siis n − k naista. Koska naisia on n kappaletta, n − k voidaan valita yhtä monella tavalla kuin  jättää  k valitsematta. Siis k miestä ja n − k naista m n sisältäviä joukkoja on kappaletta. k k  2    2  2 n  2 X 2n n n n n = . Lause 1.9. + ··· + + = n n 1 0 i i=0

Todistus. Sijoitetaan edelliseen lauseeseen m = n. Esimerkki 1.12 sisältää tapauksen n

(x + y) =

n   X n i=0

i

xi y n−i .

(2)

Tätä yhtälöä kutsutaan binomikaavaksi. Binomikaavan avulla voidaan helposti todistaa monia binomikertoimien summakaavoja.         n   X n n n n n = + + Lause 1.10. + ··· + = 2n . i 0 1 2 n i=0

Todistus. Sijoitetaan binomikaavaan (2) x = y = 1.           n X n n n n n (−1)i = − + − + · · · + (−1)n Lause 1.11. = 0. i 0 1 2 n i=0 Todistus. Sijoitetaan binomikaavaan y = 1 ja x = −1.       n   X n n n n Lause 1.12. i = +2 + ··· + n = n2n−1 . i 1 2 n i=1

Todistus. Sijoitetaan binomikaavaan y = 1 ja derivoidaan puolittain x:n suhteen, saadaan n   X n i−1 n−1 i x . n(x + 1) = (3) i i=1

Kun tähän sijoitetaan x = 1, niin saadaan väite.

1.6 Sovellus: TN-laskenta

Lause 1.13.

n X i=1

i−1

(−1)

11

        n n n n n−1 i = −2 + − · · · + (−1) n = 0. i 1 2 n

Todistus. Sijoitetaan yhtälöön (3) x = −1. Binomikaavasta saadaan monia summakaavoja derivoimalla usempaan kertaa tai integroimalla ja lopuksi sijoittamalla sopiva x. 1.6

Sovellus: TN-laskenta

Esimerkki 1.13. Millä todennäköisyydellä lotossa yhden rivin täyttämällä

saa tarkalleen a) 7 oikein, b) 6 oikein,

) 6 oikein ja lisänumero, d) 5 oikein ja lisänumero, e) 5 oikein ja ainakin 1 lisänumero?

a) Lotossa arvotaan 7 numeroa 39:stä. Lottorivejä on siis todennäköisyys sille, että rivissä on 7 oikein on

1 39
7



 39 . Täten 7

≈ 6, 5 · 10−8 .

b) Kuusi oikein rivissä taas pitää olla 6 seitsemästä arvotusta ja yksi muu    7 32 numero. Tulosäännön mukaan näitä on siis = 224 kappaletta. 6 1 Todennäköisyys on siis 224 −5 39
≈ 1, 5 · 10 . 7

) Lotossa arvotaan 7 numeron lisäksi   3 lisänumeroa. 6 ja lisänumero 7 3 rivejä on siis tulosäännön mukaan = 21. Todennäköisyys on siis 6 1

21 −6 39
≈ 1, 4 · 10 . 7

    7 3 29 d) Näitä rivejä on = 1827. Todennäköisyys on siis 5 1 1 1827 −4 39
≈ 1, 19 · 10 . 7

e) Nyt lasketaan siis ne rivit, joissa on 5  oikein yksitaikaksi  ja  lisänume  7 3 29 7 3 29 roa. Näitä rivejä on summasäännön mukaan + = 5 1 1 5 2 0

1.7 Sovellus: Virheitä korjaavat koodit

12

1890. Todennäköisyys on siis 1890 −4 39
≈ 1, 22 · 10 . 7

Opetus: kannattaa keskittyä taitopeleihin!

Esimerkki 1.14. Vakioveikkauksessa on 13 kohdetta (yleensä jalkapallo-

ottelua), joihin veikataan 1,x tai 2. Vakioveikkauksen oikea rivi ei muodostu satunnaisesti kuten lotossa, mutta oletetaan nyt, että englannissa on lumimyrsky ja oikea rivi muodostetaan arpomalla (ilman painotuksia). Millä todennäköisyydellä satunnaisesti valitussa rivissä on a) 13 oikein, b) ainakin 10 oikein?

) Kuinka monta sellaista riviä on, joissa on 9 ykköstä, 2 ristiä ja 2 kakkosta? a) Vakioveikkausrivejä on PT (3, 13) = 313 kappaletta. Todennäköisyys 13 oikein tulokselle on siis 1 ≈ 6, 3 · 10−7 . 313 (Siis n. 10 kertaa todennäköisempää kuin lotossa 7 oikein.) b) 13 oikein rivejä on 1. Rivejä, joissa on tarkalleen 12 oikein eli yksi väärin (vääriä merkkejä on kaksi vaihtoehtoa) on C(13, 1)·P (2, 1) = 13·2 =  T 13 · 22 = 312 ja 26. Tarkalleen 11 oikein rivejä on C(13, 2) · PT (2, 2) = 2   13 tarkalleen 10 oikein rivejä on C(13, 3) · PT (3, 3) = · 23 = 2288. 3 Yhteensä rivejä, joissa on 10 oikein 1 + 26 + 312 + 2288 = 2627, joten 10 oikein todennäköisyys on 2627 ≈ 0, 0016. 313

) 13 alkion joukko pitää siis partitioida kolmeen joukkoon, joiden alkioden lukumäärät ovat 9, 2 ja 2. Tämän mukaan rivejä on   13 13! = 4290. = 9!2!2! 9, 2, 2 1.7

Sovellus: Virheitä korjaavat koodit

Rajoitutaan tässä esityksessä ns. binäärisiin koodeihin. Tarkastellaan joukkoa {0, 1}n eli n-pituisten binääristen sanojen joukkoa. Sen sajoukkoa C ⊆ {0, 1}n kutsutaan koodiksi. Sanoja, jotka kuuluvat koodiin C , kutsutaan (npituisiksi) koodisanoiksi. Yleensä myös kirjoitetaan Fn2 joukon {0, 1}n sijaan. F2 on (äärellinen) kahden alkion kunta {0, 1}, missä operaatioina on yhteen- ja kertolasku modulo 2. Nyt Fn2 voidaan ajatella n-ulotteisena vektoriavaruutena yli kunnan

1.7 Sovellus: Virheitä korjaavat koodit

13

F2 . Tällä algebrallisella esityksellä pystytään tiettyjä koodien ja koodisanojen ominaisuuksia esittämään helposti. Tämä esitys voidaan yleistää myös muille äärellisille kunnille, esim. Fn3 osajoukot ovat ns. ternäärisiä koodeja. Käytetään koodisanoista merkintää v = (a1 , a2 , . . . , an ) = a1 a2 . . . an , missä ai ∈ {0, 1}, eli kirjoitetaan koodisanat vektoreina tai sanoina. Määritelmä 1.7. Koodisanan u = u1 u2 . . . un paino

w(u) = | {i | ui = 1} |, ts. paino on koodisanan ykkösten lukumäärä. Koodisanojen u = u1 u2 . . . un ja v = v1 v2 . . . vn ns. Hamming etäisyys

d(u, v) = | {i | ui 6= vi } |. Koodisanoille voidaan määritellä yhteen- ja vähennyslasku,

u + v = a1 a2 . . . an , missä ai = ui + vi , (u − v = a1 a2 . . . an , missä ai = ui − vi ). Huomaa, että binääritapauksessa yhteen- ja vähennyslasku antavat aina saman tuloksen. Nyt painolle ja etäisyydelle saadaan yhteys (4)

d(u, v) = w(u − v).

Esimerkki 1.15. Olkoon u = 010011 ja v = 010110. Nyt w(u) = 3, u−v =

000101, joten d(u, v) = 2.

Esimerkki 1.16. Kuinka paljon on a) r -painoisia n-pituisia koodisanoja? b) enintään r -painoisia n-pituisia koodisanoja?  

a) | {c ∈ Fn2 | w(c) = r} | = C(n, r) = r   X n n b) | {c ∈ F2 | w(c) ≤ r} | = . i

n . r

i=0

Määritelmä 1.8. Olkoon a jokin n-pituinen koodisana ja e ∈ N. Määritel-

lään a-keskinen e-säteinen pallo

B(a, e) = {x ∈ Fn2 | d(a, x) ≤ e} . Lemma 1.2. e-säteisen pallon alkioiden lukumäärä

Be = |B(a, e)| =

Todistus. DEMO.

e   X n i=0

i

.

1.7 Sovellus: Virheitä korjaavat koodit

14

Tarkastellaan lyhyesti tiedonsiirtoa tietoliikennekanavassa. Kanavassa lähetetään viesti m. Aluksi suoritetaan ns. koodaus, jossa m muunnetaan koodisanojen jonoksi c1 c2 . . . . Koodisanat voidaan ajatella lähetettäväksi yksi kerrallaan. Kun lähetetään koodisana c, häiriöisessä kanavassa voi tapahtua virhe v(∈ Fn2 ), jolloin vastaanottaja saa sanan c + v. Dekoodauksessa koodisanat muunnetaan takaisin viestiksi m′ .

m

koodaus

c

c+v

dekoodaus

m′

Kuva 1: Tiedonsiirtokanava. Toivottavaa tietysti on, että m ja m′ ovat samat. Koodi C ⊆ Fn2 on e virhettä korjaava, jos dekoodaus onnistuu aina oikein, kun w(v) ≤ e. Tämä tarkoittaa, että koodisana keskeiset e-säteiset pallot eivät leikkaa, siis C on e virhettä korjaava, jos

∀a, b ∈ C : a 6= b =⇒ B(a, e) ∩ B(b, e) = ∅. Määritelmä 1.9. Koodin C ⊆ Fn 2 minimietäisyys

d(C) = min {d(u, v) | u, v ∈ C, u 6= v} . Jos nyt C on e virhettä korjaava, niin d(C) ≥ 2e + 1. Koodausteoriassa pyritään löytämään mahdollisimman hyviä koodeja joidenkin annettujen kriteerien mukaan. Esimerkiksi voidaan etsiä koodia, jonka pituus on n, minimietäisyys d, ja jossa on mahdollisimman monta koodisanaa. Seuraava lause antaa koodisanojen lukumäärälle ns. Hamming-rajan (pallopakkausraja ). Lause 1.14. Olkoon C ⊆ Fn 2 koodi, jonka minimietäisyys on d = 2e + 1.

Tällöin

|C| ≤ Pe

2n

i=0

Todistus. Minietäisyyden nojalla


.

n i

(5)

|C| · Be ≤ |Fn2 | = 2n , ja nyt lemman 1.2 nojalla saadaan väite. Jos koodille C yhtälössä (5) on voimassa yhtäsuuruus, niin se on ns. täydellinen koodi.

1.7 Sovellus: Virheitä korjaavat koodit

15

Esimerkki 1.17. 7-pituisessa 3 virhettä korjaavassa koodissa on koodisa-

noja enintään

27 = 2. 1 + 7 + 21 + 35

Esimerkiksi {0000000, 1111111} on tälläinen koodi. Koodi C ⊆ Fn2 on lineaarinen, jos se on Fn2 :n aliavaruus. Lineaarisille koodeille saadaan lineaarialgebran avulla mukavia ominaisuuksia. Olkoon C ⊆ Fn2 lineaarinen koodi. Aliavaruuskriteerien mukaisesti: jos u, v ∈ C , niin u + v ∈ C . Lisäksi 0 ∈ C . Koodin minimietäisyys voidaan nyt määritellä d(C) = min {w(c) | c ∈ C \ {0}} .

Koodilla C on myös kanta, sanotaan B = {c1 , c2 , . . . , ck }, missä k = dim C . Koska kaikilla koodin C vektoreilla on yksikäsitteinen kantaesitys, niin |C| = 2k . Koodin C generoiva matriisi on   c1 c2    G =  .  ∈ F2k×n .  .. 

ck

Nyt

c ∈ C ⇐⇒ ∃u ∈ Fk2 : uG = c.


Voidaan olettaa, että G on redusoitu porrasmatriisi, ts. G = Ik P , missä P on k × (n − k)-matriisi. (n−k)×n Lineaarisella koodilla C on ns. tarkistusmatriisi H ∈ F2 , joka toteuttaa ehdon c ∈ C ⇐⇒ cH T = 0, missä H T on matriisin H transpoosi. Voidaan osoittaa, että matriisi
H = P T In−k ,

on koodin C tarkistusmatriisi. Nyt matriisin H aste r(H) = n − k. Tästä saadaan koodisanojen lukumäärälle uusi lauseke, nimittäin, jos H on C :n tarkistusmatriisi, niin

|C| = 2n−r(H) = (2n−(n−k) = 2k ). Esimerkki 1.18. Tarkastellaan koodia

 H7 = c ∈ F72 | cH T = 0 ,

1.7 Sovellus: Virheitä korjaavat koodit

missä



 0 0 0 1 1 1 1 H = 0 1 1 0 0 1 1 . 1 0 1 0 1 0 1

16

17

2 PERUSMENETELMIÄ

2.1

Lokeroperiaate

Lokeroperiaate on kaikille tuttu. Kaikessa yksinkertaisuudessaan se voidaan esittää seuraavasti:

Jos n lokerossa on enemmän kuin n palloa, niin ainakin yhdessä lokerossa on enemmän kuin yksi pallo. Ts. jos meillä on n lokeroa, n + 1 palloa, niin ainakin yhdessä lokerossa on kaksi palloa. Lokeroperiaatetta kutsutaan joskus nimellä Diri hlet'n lokeroperiaate tai kyyhkyslakkaperiaate (engl. pigeon hole prin iple). Vaikka lokeroperiaate hienoudessaan omaksutaan jo koulussa sukkien ja pallojen avulla, sitä ei pidä väheksyä. Lokeroperiaatetta käytetään monien vaikeiden teorioiden kombinatorisissa todistuksissa. Lokeroperiaatteesta esiintyy myös seuraava yleistetty muoto:

Jos n lokerossa on enemmän kuin nm palloa, niin ainakin yhdessä lokerossa on enemmän kuin m palloa. Esimerkki 2.1. Osoita, että jos joukosta {1, 2, . . . , 2n} valitaan n+1 alkioi-

nen osajoukko, niin siinä on kaksi lukua, joiden osamäärä on 2:n potenssi.

Olkoon A = {a1 , a2 , . . . , an+1 } jokin edellä mainittu n + 1 alkioinen joukko. Kirjoitetaan luvut ai muodossa

ai = ki · 2ℓi , missä ki on luvun ai suurin pariton tekijä. Luvuilla ai suurimpina parittomina tekijöinä voivat esiintyä luvut 1, 3, 5, · · · , 2n − 1. Näitä parittomia lukuja on siis n kappaletta. Jaetaan luvut ai lukujen ki mukaisesti näihin n lokeroon. Lukuja ai on n+1 kappaletta, joten lokeroperiaatteen mukaan jossakin lokerossa on ainakin kaksi lukua, sanotaan ai1 ja ai2 ja näiden osamäärä on 2ℓi1 −ℓi2 . Esimerkki 2.2. Juhlissa ihmiset kättelevät toisiaan. Osoita, että juhlien

aikana kaksi ihmistä kättelee yhtä monta ihmistä.

Esimerkki 2.3. Olkoot A ja B äärellisiä joukkoja, joille |A| = n > r = |B|,

ja f kuvaus, f : A → B . lnm −1 Osoita, että jollekin b ∈ B , |f (b)| ≥ . r

2.2 Sovellus: Kasvavat ja vähenevät osajonot

2.2

18

Sovellus: Kasvavat ja vähenevät osajonot

Tarkastellaan n-pituista reaalilukujonoa u = u1 , u2 , . . . , un , missä siis ui ∈ R. Jonon u k-pituinen osajono ui1 , ui2 , . . . uik , missä i1 < i2 < · · · < ik , on kasvava, jos ui1 < ui2 < · · · < uik ja vähenevä, jos

ui1 > ui2 > · · · > uik .

Lause 2.1. Olkoot m, n > 0. Jokainen erisuurien reaalilukujen jono

u1 , u2 , . . . , umn+1 sisältää (m + 1)-pituisen kasvavan osajonon tai (n + 1) pituisen vähenevän osajonon, tai molemmat.

Todistus. Merkitään ti :llä ui :stä alkavan pisimmän kasvavan osajonon pituutta. Jos jokin luvuista ti ≥ m + 1, väite on tosi. Oletetaan siis, että ti < m + 1 kaikilla 1 ≤ i ≤ mn + 1. Nyt siis ti :t kuuluvat joukkoon {1, 2, . . . , m} ja koska näitä lukuja on mn + 1, yleistetyn lokeroperiaatteen mukaan on olemassa vähintään n + 1 lukua i välillä 1, . . . , mn + 1, joilla on sama ti :n arvo. Merkitään näitä lukuja ui1 , ui2 , . . . , uin+1 , missä i1 < i2 < · · · < in+1 .

(6)

Tarkastellaan nyt kahta peräkkäistä lukua uij ja uij+1 . Huomataan, että uij > uij+1 , koska muuten uij :stä alkava pisin kasvava lukujono on pitempi kuin uij+1 :stä alkava, mikä on vastoin oletusta. Siis jono (6) on vähenevä (n + 1)-pituinen osajono. Tämä tulos on paras mahdollinen, sillä on olemassa mn pituisia lukujonoja, joilla ei ole (m + 1)-pituista kasvavaa tai (n + 1)-pituista vähenevää. Esimerkiksi, jos m = n = 4, niin jono,

4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13 ei sisällä viiden pituista kasvavaa tai vähenevää osajonoa. 2.3

Kaksoislaskenta

Kaksoislaskenta on lokeroperiaatteen tavoin hyvin yksinkertainen periaate. Olkoot A ja B kaksi äärellistä joukkoa ja (relaatio ) R ⊆ A × B . Jos (a, b) ∈ R, niin sanotaan, että a ja b ovat relaatiossa R. Merkitään αa :lla a:n kanssa (a ∈ A) relaatiossa olevien B :n alkioiden lukumäärää ja βb :llä vastaavasti b:n kanssa (b ∈ B ) relaatiossa olevien A:n alkioiden lukumäärää. Nyt X

a∈A

αa = |R| =

X

b∈B

βb (kaksoislaskenta ).

2.4 Sovellus: Jakajien lukumäärän keskiarvo

19

Kaksoislaskennan yhtälö on itsestään selvä. Se osoittautuu kuitenkin hyväksi menetelmäksi joissain tapauksissa. Esimerkki 2.4. Osoitetaan, että

1 + 2 + ··· + n =

n(n + 1) 2

tarkastelemalla relaatiota R = {(x, y) | x < y} ⊆ {1, 2, . . . , n + 1}2 . Kaksoislaskenta voidaan tulkita myös toisella tavalla. Olkoon A = {a1 , a2 , · · · , am } ja B = {b1 , b2 , . . . , bn }. Relaation R ⊆ A × B relaatiomatriisi on m × n-matriisi MR , jossa alkio ( 1, jos (ai , bj ) ∈ R, (i, j) = 0, muulloin. Kaksoislaskentayhtälön mukaan matriisin MR ykkösten määrä on sama laskettuna vaakariveittäin tai pystyriveittäin. 2.4

Sovellus: Jakajien lukumäärän keskiarvo

Tarkastellaan kaksoislaskennan sovelluksena luonnollisten lukujen jakajien keskiarvoa. Olkoon An = {1, 2, . . . , n} ja relaatio R = {(i, j) | i|j} ⊆ An × An , missä merkintä i|j tarkoittaa, että "i jakaa j :n". Tarkastellaan matriisia MR . Alla esimerkki tapaus n = 8   1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1   0 0 1 0 0 1 0 0   0 0 0 1 0 0 0 1   0 0 0 0 1 0 0 0 .   0 0 0 0 0 1 0 0   0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1

Tarkastellaan funktiota t(i), joka antaa luvun i jakajien lukumäärän. Jos i on alkuluku, t(i) = 2, ja jos i = 2k , niin t(i) = k + 1. Funktion t arvot siis vaihtelevat paljon. Entäpä jakajien lukumäärän keskiarvo? Merkitään funktion t keskiarvoa joukossa An t¯(n):llä, siis n

1X t¯(n) = t(i). n

(7)

i=1

Keskiarvo t¯(n) saadaan matriisista MR laskemalla ykkösten lukumäärä ja jakamalla n:llä. Määritelmässä (7) tämä on tehty pystyriveittäin. Laskejnk i. taan samat ykköset vaakariveittäin: luku i jakaa luvut 1i, 2i, 3i, . . . , i

2.5 Seulaperiaate

Jokaisella vaakarivillä on siis

jnk i

20

ykköstä, ja

n

n

i=1

i=1

 1 X jnk 1 X n t¯(n) = = − ci , n i n i missä 0 ≤ ci < 1 kaikille i ∈ {1, 2, . . . , n}. Näin ollen yhteen laskettu virhe summassa on alle n, joten keskiarvossa virhe on alle 1. Saatiin siis, että n

n

i=1

i=1

X1 1Xn −c= − c = Hn − c, t¯(n) = n i i missä 0 ≤ c < 1. Analyysin kursseilta tiedetään, että harmoonisen sarjan osasummalle Hn on voimassa, että

ln n +

1 < Hn < ln n + 1, n

joten saadaan, että

ln n + ja siis

1 − c < t¯(n) < ln n + 1 − c, n

ln n − 1 < t¯(n) < ln n + 1,

Saadaan siis, että t¯(n) poikkeaa ln n:stä siis alle 1 verran. Nyt siis

t¯(n) = 1. n→∞ ln n lim

Yleensä merkitään t¯(n) ∼ ln n. 2.5

Seulaperiaate

Edellisessä luvussa esitetyn summasäännön nojalla

|A1 ∪ A2 ∪ · · · ∪ An | = |A1 | + |A2 | + · · · + |An |, jos joukot Ai ovat erillisiä. Tarkastellaan nyt tapausta, jossa erillisyys-ehto ei välttämättä ole voimassa. On helppo osoittaa, että

|A ∪ B| = |A| + |B| − |A ∩ B|. Yleistetään tämä useammalle joukolle seuraavassa lauseessa. Sen laskenta menetelmää kutsutaan seulaperiaatteeksi (engl. prin iple of in lusion and ex lusion).

2.5 Seulaperiaate

21

Esitellään aluksi merkinnät. Olkoot Ai , 1 ≤ i ≤ n, äärellisiä joukkoja. Merkitään

S1 = |A1 | + |A2 | + · · · |An |, S2 = |A1 ∩ A2 | + |A1 ∩ A3 | + · · · = S3 = |A1 ∩ A2 ∩ A3 | + · · · = .. .

X

X i deg p(x), ja

oletetaan, että g(x)−1 ∈ C[[x]]. Jos α1 , . . . , αk ovat polynomin g(x) erisuuret nollakohdat ja αi on kertalukua mi , niin on olemassa sellaiset luvut cij ∈ C, että c11 c12 c1m1 p(x) = + + ··· + 2 g(x) (α1 − x) (α1 − x) (α1 − x)m1 c21 c22 c2m2 + + + ··· + + ··· 2 (α2 − x) (α2 − x) (α2 − x)m2 ckmk ck2 ck1 + + ··· + + 2 (αk − x) (αk − x) (αk − x)mk

(29)

Todistus. Sivuutetaan. p(x) osamurg(x) tokehitelmäksi. Osamurtokehitelmän luvut cij etsitään ns. määräämättömien kerrointen menetelmällä. Huomaa myös, että koska g(x)−1 on olemassa, niin g(x):n vakiotermi ei ole 0, joten αi 6= 0 kaikilla 1 ≤ i ≤ k. Yhtälön (29) oikeaa puolta kutsutaan rationaalipolynomin

1 osamurtokehitelmä. 1 − x2 Koska 1 − x2 = (1 − x)(1 + x), niin edellisen lauseen mukaan

Esimerkki 4.14. Etsi rationaalipolynomin

a b 1 + . = 1 − x2 1−x 1+x Kun nyt kerrotaan puolittain (1 − x2 ):lla, saadaan yhtälö 1 = a(1 + x) + b(1 − x) = a + b + (a − b)x, josta voidaan ratkaista a ja b. Nimittäin, a + b = 1 1 ja a − b = 0, joten a = b = . Siis 2

1 1 1 1 1 = + 1 − x2 21−x 21+x

4.4 Laskusäännöt

46

Rationaalipolynomin määrittelemän funktion potenssisarjamuoto saadaan ratkaistua, kun etsitään rationaalipolynomin osamurtokehitelmä ja käyte1 tään apuna sarjojen sarjamuotoa. Voidaan nimittäin osoittaa, et(1 − cx)n tä yhtälö (29) voidaan kirjoittaa muotoon

p(x) b12 b1m1 b11 + + ··· + = −1 −1 2 m1 g(x) (1 − α1 x) (1 − α1 x) (1 − α−1 1 x) b21 b22 b2m2 + + + ··· −1 −1 2 + · · · + m2 (1 − α2 x) (1 − α2 x) (1 − α−1 2 x) bkmk bk2 bk1 + + , −1 −1 2 + · · · + mk (1 − αk x) (1 − αk x) (1 − α−1 k x)

missä bij ∈ C.

Esimerkki 4.15. Etsitään rationaalipolynomin

x määrittele1 − 5x + 6x2

män potenssisarjan sarjamuoto. 1 1 1 − 5x + 6x2 = 6(x − )(x − )(= (1 − 2x)(1 − 3x)), joten 2 3

a b x = + . 1 − 5x + 6x2 1 − 2x 1 − 3x

Kun kerrotaan yhtälö puolittain 1 − 5x + 6x2 :lla, saadaan, että x = a(1 − 3x) + b(1 − 2x). Yhtälön kertoimista seuraa kaksi yhtälöä, a + b = 0 ja −3a − 2b = 1, joista saadaan, että a = −1, b = 1. Olemme siis saaneet, että

x 1 1 + =− 1 − 5x + 6x2 1 − 2x 1 − 3x ∞ ∞ ∞ X X X (3i − 2i )xi (3x)i = (2x)i + =− i=0

i=0

Huomaa, että 4.4

i=0

x on siis jonon (3n − 2n )∞ n=0 generoiva funktio. 1 − 5x + 6x2

Laskusäännöt

Käydään seuraavaksi läpi generoivien funktioiden laskusääntöjä. ∞ Olkoon (an )∞ n=0 lukujono ja f (x) sen generoiva funktio. Jonon (an+1 )n=0 generoiva funktio on ∞ X

n=0

∞

an+1 xn =

1X f (x) − a0 an xn = . x x n=1

Jatkamalla samaa päättelyä, saadaa, että jonon (an+2 )∞ n=0 generoiva funktio on f (x)−a0 − a1 f (x) − a0 − a1 x x = . x x2

4.4 Laskusäännöt

47

∞ Sääntö 1. Jos f (x) on jonon (an )∞ n=0 generoiva funktio, niin jonon (an+k )n=0

generoiva funktio on

f (x) − a0 − a1 x − · · · − ak−1 xk−1 . xk Esimerkki 4.16. Olkoon f (x) Fibona

in lukujen Fn generoiva funktio.

Säännön 1, palautuskaavan Fn+2 = Fn+1 + Fn ja alkuehtojen F0 = 1, F1 = 1 avulla saadaan generoivalle funktiolle f yhtälö

f (x) − 1 f (x) − x − 1 + f (x). = 2 x x Oikea puoli saadaan summaperiaatteella. Kun tästä ratkaistaan f (x), saadaan, että 1 . f (x) = 1 − x − x2

∞ Olkoon taas (an )∞ n=0 lukujono ja f (x) sen generoiva funktio. Jonon (nan )n=0 generoiva funktio on ! ∞ ∞ ∞ X X X an xn = x(Df (x)) = xDf (x). nan xn−1 = xD nan xn = x n=0

n=0

n=1

Merkitään (xD):llä operaatiota, jossa ensin derivoidaan ja sitten kerrotaan x:llä. Tämä operaatio voidaan tietysti yleistää muotoon: jonon (nk an )∞ n=0 generoiva funktio on

(xD)(xD) · · · (xD)f (x) = (xD)k f (x). {z } | k kpl

Summaperiaatteen mukaan saadaan seuraava sääntö:

Sääntö 2. Jos f (x) on jonon (an )∞ n=0 generoiva funktio ja p on jokin poly-

nomi, niin jonon (p(n)an )∞ n=0 generoiva funktio on

p(xD)f (x). Esimerkki 4.17. Mikä on jonon (3 − n2 )∞ n=0 generoiva funktio?

Jonon (1)∞ n=0 generoiva funktio on f (x) =

jonon (3 − n2 )∞ n=0 generoiva funktio on

1 . Säännön 2 mukaan 1−x

3 x 1 = − (xD) 1−x 1−x (1 − x)2 ! 3 1 2x 3 − 7x + 2x2 = −x + . = 1−x (1 − x)2 (1 − x)3 (1 − x)3

(3 − (xD)2 )f (x) = (3 − (xD)2 )

4.4 Laskusäännöt

Esimerkki 4.18. Lasketaan summa

48

∞ X n2 + 4n + 5

n!

n=0  ∞

.

1 Esimerkin 4.13 mukaan jonon generoiva funktio on ex . Säännön n! n=0  ∞ 2 mukaan siis jonon (n2 + 4n + 5)/n! generoiva funktio on siis n=0

((xD)2 + 4(xD) + 5)ex = (x2 + 4x + 5)ex .

Kun tähän sijoitetaan x = 1, saadaan tulos ∞ X n2 + 4n + 5

n!

n=0

= 10e.

Huomaa, että sarjan (tässä tapauksessa ex ) tulee olla suppeneva sijoitetulla x:n arvolla. Seuraavat säännöt koskevat generoivien funktioiden tuloa. Sääntö 3. Jos f (x) on jonon (an )∞ n=0 generoiva funktio ja g(x) on jonon

(bn )∞ n=0 generoiva funktio, niin f (x)g(x) on jonon !∞ n X ar bn−r r=0

n=0

generoiva funktio. k Sääntö 4. Jos f (x) on jonon (an )∞ n=0 generoiva funktio, niin (f (x)) on

jonon

X

n1 +n2 +···nk =n

generoiva funktio.

an1 an2 · · · ank

!∞

n=0

Esimerkki 4.19. Olkoon r(n, k) yhtälön

x1 + x2 + · · · + xn = k ei-negatiivisten kokonaislukuratkaisujen lukumäärä. Koska jonon (1)∞ n=0 ge1 neroiva funktio on , niin Säännön 4 mukaan jonon (r(n, k))∞ n=0 gene1−x roiva funktio on  ∞  X n+k−1 k 1 = x . (1 − x)n k k=0

Tämä tulos oli tosin tiedossa jo Lauseen 1.2 mukaan.

4.5 Rekursiot ja generoivat funktiot

49

Jos f (x) on jonon (an )∞ n=0 generoiva funktio, niin

f (x) = (a0 + a1 x + a2 x2 + · · · )(1 + x + x2 + · · · ) 1−x = a0 + (a0 + a1 )x + (a0 + a1 + a2 )x2 + (a0 + a1 + a2 + a3 )x3 + · · · joten saadaan Sääntö 5. Jos f (x) on jonon (an )∞ n=0 generoiva funktio, niin

f (x) 1−x

on jonon

n X i=0

generoiva funktio.

ai

!∞

n=0

Esimerkki 4.20. Etsi harmonisten lukujen Hn =

n X 1 i=1

i

muodostaman jonon

(Hn )∞ n=1 generoiva funktio. 5 mukaan jonon generoiva funktio saadaan  1 Säännön  1 ∞ kertomalla jonon ∞ 1 generoiva funktio funktiolla . Jonon generoiva funktio n n=1 1−x n n=1 on ∞ X 1 n x = g(x). n n=1

1 , joten g(x) = − ln(1 − x) (tämä näkyy myös funk1−x tion ln(1 + x) Taylorin sarjasta). Säännön 5 mukaan Selvästi D(g(x)) =

∞ X

n=1

4.5

Hn xn =

 1  1 . ln 1−x 1−x

Rekursiot ja generoivat funktiot

Tarkastellaan seuraavaksi palautuskaavojen ratkaisemista generoivien funktioiden avulla. Olkoon (un )∞ n=0 lukujono, joka toteuttaa jonkin palautuskaavan. Ratkaisu löydetään seuraavan algoritmin avulla: (i) Etsitään jonon (un )∞ n=0 palautuskaavan avulla jonon generoivaa funktiota U (x) koskeva yhtälö. Yleensä yhtälö saadan sijoitamalla generoivan yhtälön sarjamuotoon alkuehdot ja palautuskaava, tai se muodostetaan palautuskaavasta edellä olleiden viiden laskusäännön avulla. (ii) Ratkaistaan saadusta yhtälöstä U (x).

4.5 Rekursiot ja generoivat funktiot

50

(iii) Etsitään funktion U (x) sarjamuoto, yleensä osamurtokehitelmän avulla. Kertoimista nähdään rekursion ratkaisu. Esimerkki 4.21. Ratkaistaan rekursio un = un−1 + n, u0 = 1.

(i): U (x) =

∞ X

un xn = 1 +

=1+x

(un−1 + n)xn = 1 +

n=1 ∞ X

n=0 ∞ X

∞ X

un xn +

∞ X

un xn+1 +

(n + 1)xn+1 = 1 + xU (x) + x

(iii): U (x) =

=

n

x +x

n=0 ∞  X

n=0

 ∞  X n+2

n=0

n

n(n + 1)  n 1+ x 2

Siis saatiin, että un = 1 +

∞ X

(n + 1)xn

n=0

1 x = 1 + xU (x) + (xD) = 1 + xU (x) + 1−x (1 − x)2 x (ii): U (x) = 1 + xU (x) + ⇐⇒ (1 − x)2 1 + x(1 − x)−2 1 x U (x) = = + . 1−x 1 − x (1 − x)3 ∞ X

nxn

n=0

n=0

n=0

n=0

∞ X

  ∞  X n+1  n x 1+ x = n−1 n

n=0

1 n(n + 1) = (n2 + n + 2). 2 2

Esimerkki 4.22. Ratkaistaan Fibona

in lukujen rekursio.

Todistetaan seuraavaksi Lause 3.1. Olkoon (un )∞ n=0 lukujono, joka toteuttaa palautuskaavan

( u0 = b0 , u1 = b1 , . . . , uk−1 = bk−1 , un+k + a1 un+k−1 + a2 un+k−2 + · · · + ak un = 0

(n ≥ 0),

(30)

missä ak 6= 0. Aloitetaan jonon generoivaa funktiota koskevalla lauseella Lause 4.3. Palautuskaavan (30) määrittelemän jonon (un )∞ n=0 generoiva

funktio

U (x) =

r(x) , 1 + a1 x + a2 x2 + · · · + ak xk

missä r(x) on polynomi, jonka deg r(x) < k. Alkuehdot (30) määräävät r(x):n kertoimet yksikäsitteisesti.

4.5 Rekursiot ja generoivat funktiot

51

Todistus. Olkoon U (x) jonon (un )∞ n=0 generoiva funktio. Nyt (1 + a1 x + a2 x2 + · · · + ak xk )U (x) = (1 + a1 x + a2 x2 + · · · + ak xk ) k−1

= u0 + (u1 + a1 u0 )x + · · · + (uk−1 + a1 uk−2 + · · · + ak−1 u0 )x ∞ X (un+k + a1 un+k−1 + a2 un+k−2 + · · · + ak un )xn+k +

∞ X

un xn

n=0

n=0

= u0 + (u1 + a1 u0 )x + · · · + (uk−1 + a1 uk−2 + · · · + ak−1 u0 )xk−1 = r(x).

Huomaa, että r(x):n kertoimet seuraavat alkuehdoista. Tarkastellaan jonon (30) karakteristista yhtälöä,

xk + a1 xk−1 + · · · + ak = 0. Jos r1 , r2 , . . . , rm ovat jonon erisuuret karakteristiset juuret, niin saadaan yhtälö

xk + a1 xk−1 + · · · + ak = (x − r1 )j1 (x − r2 )j2 · · · (x − rm )jm . Kerrotaan tämä yhtälö puolittain x−k :lla, saadaan

1 + a1 x−1 + · · · + x−k ak = (1 −

r1 j1 r2 rm jm ) (1 − )j2 · · · (1 − ) . x x x

Tehdään nyt muuttujanvaihdos, kirjoitetaan x :=

1 , saadaan yhtälö x

1 + a1 x1 + · · · + xk ak = (1 − r1 x)j1 (1 − r2 x)j2 · · · (1 − rm x)jm . Edellisen lauseen tulos voidaan nyt siis kirjoittaa muotoon

U (x) =

(1 − r1

x)j1 (1

r(x) . − r2 x)j2 · · · (1 − rm x)jm

(31)

Nyt olemme valmiit todistamaan Lauseen 3.1. Kirjoitetaan se seuraavaan muotoon. Lause 3.1. Olkoot r1 , r2 , . . . , rm rekursion karakteristisen yhtälön erisuuret

juuret, ri kertalukua ji , kaikilla 1 ≤ i ≤ m. Tällöin rekursion yleinen ratkaisu on n un = p1 (n)r1n + p2 (n)r2n + · · · + pm (n)rm , missä kukin pi (n) on enintään astetta ji − 1 oleva polynomi.

4.6 Sovellus: Catalanin luvut

52

Todistus. Osoitetaan, että kaikkillla alkuehdoilla jono un on lauseen väitteen muotoa. Yhtälön (31) ja Lauseen 4.2 mukaan on olemassa sellaiset luvut γit , että ji m X X

γit (1 − ri x)t i=1 t=1   ! ji m X ∞ X X n+t−1 n n γit ri x . = n

U (x) =

n=0

Siis missä

i=1 t=1

n un = p1 (n)r1n + p2 (n)r2n + · · · + pm (n)rm ,

pi (n) =

ji X

γit

t=1



n+t−1 n



on n:n suhteen enintään astetta ji − 1 oleva polynomi. 4.6

Sovellus: Catalanin luvut

Tarkastellaan esimerkkinä generoivien funktioiden käytöstä ns. Catalanin lukuja f (n). Näille luvuille on olemassa useita erilaisia määritelmiä tai oikeastaan on olemassa lukuisia eri laskentaongelmia, joiden ratkaisuna Catalanin luvut ovat. Käytetään seuraavaa määritelmää luvuille f (n): annettuna n sulkuparia, luku f (n) ilmoittaa kuinka monella tavalla ne voidaan järjestää laillisesti. Sulkujen muodostama sana on laillinen, jos siinä vasemmalta oikealle luettaessa ei missään kohtaa ole luettuna enempää oikeaa kuin vasenta sulkua. Esimerkiksi, jos n = 3, niin lailliset sulkusanat ovat

((())), (()()), (())(), ()()(), ()(()).

(32)

Siis f (3) = 5. Lisäksi sovitaan, että f (0) = 1. Seuraavaksi muodostetaan luvuille f (n) palautuskaava. Olkoon w jokin laillinen n sulkuparin muodostama sana, ts. |w| = 2n. Liitetään nyt jokaiseen lailliseen n sulkuparin sanaan kokonaisluku k seuraavasti: k pienin sellainen kokonaisluku, että sanan w 2k-pituisessa alkuosassa on k sulkuparia. Ts. tämä alkuosa on laillinen k sulkuparin muodostama sana. Esimerkiksi sanoille (32) luvut k ovat 3, 3, 2, 1 ja 1, vastaavasti. Sana w on primitiivinen sulkusana, jos k = n. Merkitään g(n):llä laillisten primitiivisten n sulkuparin sanojen lukumäärää. Lemma 4.1. Jos k ≥ 1, niin

g(k) = f (k − 1).

4.6 Sovellus: Catalanin luvut

53

Todistus. Jokaisesta laillisesta (k − 1) sulkuparin sanasta saadaan k sulkuparin primitiivinen sana lisäämällä alkuun vasen ja loppuun oikea sulku. Toisaalta jokaisesta primitiivisestä k sulkuparin primitiivisestä saadaan laillinen (k−1) sulkuparin sana poistamalla ensimmäinen ja viimeinen sulku. Tarkastellaan nyt laillisia n-sulkuparin sanoja lukuja k kohti. Nämä ovat siis sanoja, joissa on alussa jokin k sulkuparin primitiivinen sulkusana ja sen jälkeen mikä tahansa (n − k) sulkuparin sana. Siis näitä sanoja on

g(k)f (n − k) = f (k − 1)f (n − k). Nyt saamme muodostettua luvuille f (n) palautuskaavan, kun summataan yli kaikkien mahdollisten lukujen k, ts.

f (n) =

n X k=1

f (k−1)f (n−k) = f (0)f (n−1)+f (1)f (n−2)+· · ·+f (n−1)f (0).

Olkoon F (x) jonon (f (n))∞ n=0 generoiva funktio. Nyt siis

F (x) = 1 +

∞ X n X

n

f (k − 1)f (n − k)x = 1 +

n=1 k=1 ∞ n−1 X X

=1+x

n=1 k=0

∞ n−1 X X

n=1 k=0

f (k)f ((n − 1) − k)xn

f (k)f ((n − 1) − k)xn−1 = 1 + xF (x)2 .

Tästä saadaan yhtälö

xF (x)2 − F (x) + 1 = 0,

(33)

josta voidaan ratkaista F (x),

F (x) =

1±

√ 1 − 4x . 2x

Tässä nimittäjässä olevalla potenssisarjalla 2x ei ole käänteisalkiota. Lemman 4.1 nojalla jonon (g(n))∞ n=0 generoivalle funktiolla G(x) on tiedossa, että G(x) = xF (x), kun g(0) = 0. Kerrotaan yhtälö (33) puolittain x:llä ja sijoitetaan xF (x) = G(x). Saadaan siis, että

G(x)2 − G(x) + x = 0. Ratkaistaan tästä jonon (g(n)) generoiva funktio √ 1 ± 1 − 4x G(x) = . 2

4.7 Eksponentiaalinen generoiva funktio

54

Kirjoitetaan oikeapuoli auki, ja koitetaan päätellä onko merkki + vai −. ! 1 ∞ X 1 1 1 G(x) = (1 ± (1 − 4x) 2 ) = (−1)n 2 (4x)n 1± n 2 2 n=0 !   ∞ X 1 1 2n − 2 2n n − 2n−1 = 1±1± 2 x , 2 n2 n−1 n=1

ja koska g(0) = 0, merkki on − ja

!   ∞ 1X 1 2n − 2 2n n G(x) = − − 2n−1 2 x , n−1 2 n2 n=1   ∞ X 1 2n − 2 n x . = n n−1 n=1 Nyt siis

F (x) =

∞ X

n=0

ja

f (n) =

  1 2n n x , n+1 n

  2n 1 . n+1 n

Huomautus 7. Catalanin luvut määritellään joissain lähteissä sellaisten

laillisten sulkusanojen lukumääräksi, joissa uloimmat sulkeet ovat yli koko sanan, ts. lasketaan vain primitiiviset sulkusanat. Tällöin Catalanin luvut ovat siis edellisen nojalla   1 2n − 2 g(n) = f (n − 1) = . n n−1 Esimerkki 4.23. Määritellään xy -tasossa seuraavat siirrot kokonaislukupis-

teistä toiseen, Y : (x, y) → (x + 1, y + 1) ja A : (x, y) → (x + 1, y − 1). Kuinka monta sellaista polkua on origosta (0, 0) pisteeseen (2n, 0) käyttäen näitä siirtoja, että missään kohtaa polulla ei mennä x-akselin alapuolelle? Entä jos x-akselin sivuaminenkin kielletään? 4.7

Eksponentiaalinen generoiva funktio

Määritelmä 4.3. Jonon (un )∞ n=0 eksponentiaalinen generoiva funktio

E(x) =

∞ X

n=0

un

xn . n!

4.8 Sovellus: Derangement-ongelma

55

Esimerkki 4.24. Jonon (1)∞ n=0 ekponentiaalinen generoiva funktio on

ex = 1 + x + Funktio

x2 x3 + + ··· . 2! 3!

1 on jonon (n!)∞ n=0 eksponentiaalinen generoiva funktio, sillä 1−x ∞

∞

n=0

n=0

X n! X 1 xn = = xn . 1−x n!

Yhteen- ja kertolasku tapahtuvat samalla tavalla kuin tavallisille generoiville funktioille. Eksponentiaalisille generoiville funktioille voidaan todistaa laskusääntöjä aivan kuten tavallisille generoiville funktioille. Rajoitutaan tässä kuitenkin seuraavaan esimerkkiin. 4.8

Sovellus: Derangement-ongelma

Tarkastellaan uudelleen ns. derangement-ongelmaa, joka ratkaistiin jo pykälässä 2.6. Tarkastellaan joukon Sn permutaatiota α. Olkoon

| {i | α(i) = i, 1 ≤ i ≤ n} | = k, ts. k alkiota kuvautuu itsekseen (näitä kutsutaan α:n kiintopisteiksi ). Nyt loput n − k alkiota eivät siis kuvaudu itsekseen, joten ne muodostavat siis (n−k)   alkion derangement permutaation. k kiintopistettä taas voidaan valita n tavalla, joten saadaan, että k n   X n n! = Dn−k (n ≥ 0). k k=0

Ajatellaan tämän yhtälön vasen- ja oikeapuoli jonoina. Vasemman puolen 1 eksponentiaalinen generoiva funktio on . Tarkastellaan seuraavaksi oi1−x kean puolen jonon generoivaa funktiota. Olkoon D(x) jonon (Dn )∞ n=0 eksponentiaalinen generoiva funktio. Nyt ! ! ! ! n   ∞ n ∞ X X X X n n! Dn−k /n! xn = Dn−k /n! xn k k!(n − k)! n=0 n=0 k=0 k=0 ! ∞ ∞ ∞ n X 1 X Di X X 1 Dn−k xn = xn xi = ex D(x). = k! (n − k)! n! i! n=0

k=0

Saadaan siis yhtälö

n=0

i=0

1 = ex D(x), 1−x

4.8 Sovellus: Derangement-ongelma

56

ja kun ratkaistaan D(x), saadaan ∞

∞

∞

X X X e−x 1 D(x) = (−1)n xn xi = = 1 − x n=0 n! n=0 i=0

! n X 1 xn . (−1)k k! k=0

Nyt kun tarkastellaan molempien puolien xn -termin kertoimia, saadaan, n

Dn X 1 (−1)k , = n! k! k=0

josta jo pykälässä 2.6 saatu tulos derangement-permutaatioiden lukumääräksi seuraa, nimittäin ! n X (−1)k . Dn = n! k! k=0