Diskreetti matematiikka / kevät 2012

Harjoitus 4, viikko 19

1. Ratkaise rekursioyhtälö:

a_n = 2a_n-1 + n, n ³ 1, a₀ = 1.

2. Portaikossa voi nousta 1 tai 2 askelmaa kerrallaan.Laadi rekursioyhtälö, joka

kuvaa montako erilaista tapaa on nousta ylös n-askelmainen portaikko.

3. L. Fibonaccin kanitarhassa asuu tammikuun 1202 alussa kaksi vastasyntynyttä

kaniparia, ja helmikuussa isäntä hankkii näiden seuraksi vielä kolmannen,

kuukautta nuoremman parin. Kukin kanipari tuottaa kahden kuukauden ikäisenä

uuden parin, ja tämän jälkeen uuden parin aina kuukauden välein. Fibonaccin

kanit elävät ikuisesti. Montako kaniparia tarhassa asuu kuukauden n alussa?

4. L Fibonacci on päättänyt laajentaa toimintaansa kettutarhaukseen. Kukin

kettupari tuottaa uuden parin 1 vuoden ikäisenä, toisen parin 2 vuoden ikäisenä,

ja kuolee ennen 3. ikävuottaan lisääpentuja tuottamatta. Montako kettuparia

asuu Fibonaccin kettutarhassa vuoden 1203+n alussa, kun tarha aloittaa yhdellä

vastasyntyneellä parilla vuoden 1023 alussa?

5. Piirrä täydellinen kaksijakoinen verkko K_2,4 ja esitä sen naapurimatriisi.

Minkälaisia ovat yleisesti verkkojen K_n, K_m,n ja C_n naapurimatriisit?

6. Piirrä kaikki keskenään ei-isomofiset 4-solmuiset (suuntaamattomat,

yksinkertaiset) verkot.