اگر $f_n$ تعداد جایگشت های$1$ تا $n$ باشد که هر عد از عدد مجاور خود حداکثر دو واحد اختلاف دارد $f_n$را بیابید

Question

اگر $f_n$ تعداد جایگشت های$1$ تا $n$ باشد که هر عد از عدد مجاور خود حداکثر دو واحد اختلاف دارد رابطه بازگشتی برای $f_n$ بیابید.

جواب کتاب $f_n=f_{n-1}+f_{n-3}+1$

Comments

@Taha۱۳۸۱ پاسخ کتاب اشتباه است (یا اشتباه نوشته‌اید). زیرا اگر برای ۴ مقدار نخست امتحان می‌کردید $f_1=1,\;f_2=2,\;f_3=6,\;f_4=12$. در حالیکه فرمول شما می‌گوید $f_4=f_3+f_1+1=6+1+1=8$ که اشتباه است.
مقدار $f_n$ را می‌توانید بوسیلهٔ هندسهٔ جبری برای $n$-ِ داده‌شده بیابید ولی چون رابطهٔ بازگشتی خواسته‌اید فکر نکنم به این روش هندسهٔ جبری علاقه داشته‌باشید.