Bu soruyu değişik yollardan çözmek mümkün. En basitinden bütün sıçrama şekilleri sayılabilir. Ben de çözüme bu şekilde başlayayım. 10 sayısını 1 ve 2 sayılarının toplamı şeklinde kaç değişik şekilde yazabiliriz? Bu arada bu toplamları 1 ve 2 adımlık sıçramaların sıraları da önemli olacak şekilde yazacağız. Yani 1+2+2+2+2+1 ile 1+1+2+2+2+2 toplamlarını farklı sıçramalar olarak sayacağız.
[table id=18 /]
Bu tablonun son sütunundaki toplamları topladığımızda da:
1 + 9 + 28 + 35 + 15 + 1 = 89 değişik sıçrama yöntemi buluruz.
Açıklamalar kısmında uzun uzun listelediğim sıçramaları bir önceki sütunda kombinasyon adetlerini bulma formülüyle kolayca hesaplayabiliriz tabii ki.
Soruyu başka türlü de çözebilirdik tabii ki. Bunun için önce daha küçük bir soruyla başlayalım. Bir basamak olsun. Tabii ki kurbağa bu merdiveni sadece tek bir sıçramayla çıkabilir. Peki iki basamak olursa ne olur? Bu da kolay, ya bir ya da iki basamak sıçrayarak iki değişik şekilde çıkar.
Üç basamağa geldi sıra. Kurbağa birinci basamaktan iki adımlık sıçramayla üçüncü basamağa ulaşabilir ya da ikinci basamaktan tek adımda. Yani üçüncü basamağa geliş yolu sayısı birinci basamağa geliş yolu sayısıyle ikinci basamağa geliş yolu sayısının toplamı oluyor.
Dördüncü basamak için baktığımızda da aynı şekilde üçüncü basamağa geliş yollarıyla ikinci basamağa geliş yollarının toplamını bulacağız. Bunu genel olarak yazmaya kalkarsak da şöyle bir şey çıkacak:
\(F(n) = F(n-1) + F(n-2) \)
n merdivendeki basamak sayısı, F(n) de kurbağanın bu merdiveni kaç farklı yoldan çıkabileceğinin sayısı. Yukarıdaki formül Fibonacci dizilerinin ta kendisi olmaktadır. Bu formülü defalarca kullanarak da soruyu çözebiliriz.
\(F(1) = 1 \)
\(F(2) = 2 \)
\(F(3) = F(2) + F(1) = 2 + 1 = 3 \)
\(F(4) = F(3) + F(2) = 3 + 2 = 5 \)
\(F(5) = F(4) + F(3) = 5 + 3 = 8 \)
\(F(6) = F(5) + F(4) = 8 + 5 = 13 \)
\(F(7) = F(6) + F(5) = 13 + 8 = 21 \)
\(F(8) = F(7) + F(6) = 21 + 13 = 34 \)
\(F(9) = F(8) + F(7) = 34 + 21 = 55 \)
\(F(10) = F(9) + F(8) = 55 + 34 = 89 \)
Bu şekilde de 89 çözümü bulunabiliyor.