Úkoly z Kombinatoriky a grafů, 5. série

Veškerá tvrzení precizně zdůvodněte.

(5.1) Kolik je permutací n prvků s právě k pevnými body? 4 body

(5.2) Navrhněte algoritmus, který spočítá n-té Fibonacciho číslo v čase O(logn). Součástí řešení má být podrobný slovní popis, analýza složitosti, případně důkaz správnosti a zápis algoritmu v pseudokódu. Slovo nápovědy: matice.

5 bodů