Fibonacci üzrə qeyri-müəyyənlik

Tam ədədlərin Fibonacci sistemində təqdimatı üçün baza olaraq 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... ədədləri istifadə olunur. Yəni, F(2)-dən başlayaraq ardıcıl olaraq bütün Fibonacci ədədləri nəzərə alınır. Bu sistemdə tam ədədin yazılışı, ən kiçik (sağ) rəqəmi 1 ədədinə, növbəti isə 2 ədədinə və s. uyğun gələn ikilik kombinasiyadır. 1 rəqəmi müvafiq baza üzvünün bu ədədə öz töhfəsini (öz böyüklüyünə bərabər) verdiyini, 0 isə müvafiq baza elementinin bu ədədin yazılışına öz töhfəsini vermədiyini göstərir. Məsələn, (101001)_f yazılışı 1·1+0·2+0·3+1·5+0·8+1·13=19 ədədini ifadə edir. Asanlıqla müşahidə etmək olar ki, standart ikilik sistemdən fərqli olaraq, Fibonacci sistemində ədədlərin təqdimatı birmənalı deyil. Məsələn, yuxarıda göstərilən 19 ədədi bu sistemdə (11111)_f kimi də yazıla bilər.

Verilmiş tam N ədədinin Fibonacci sistemində müxtəlif təqdimatlarının sayını müəyyən edin.