شمارش با رابطه‌ی بازگشتی، سطح۱

یکی از ابزارهای شمارش رابطه‌ی بازگشتی است. گاهی ممکن است نتوانیم خیلی ساده بشماریم ولی بتوانیم مورد شمارش را بر حسب مساله‌هایی کوجک‌تر از نوع خودش حساب کنیم. مثلا هدف پیدا کردن مقدار h₁ است ولی ما تنها می‌توانیم h₁ را بر حسب h₂ پیدا کنیم. شاید معروف‌ترین مساله‌ی بازگشتی مساله‌ی برج هانوی باشد. این مساله را لوکاس ریاضیدان فرانسوی قرن نوزدهم مطرح کرد. سه میله داریم و در میله‌ی نخست n صفحه‌ی گرد هم هیچ دو تایی هم اندازه نیستند و هر کدام یک سوراخ در مرکز دارد هست. همه‌ی صفحه‌ها روی هم هستند و هیچ صفحه‌ای روی صفحه‌ی کوچک‌تر از خود نیست. هدف این است که همه‌ی این صفحه‌ها را به میله‌ی سوم ببریم. هنگام جا به جایی صفحه‌ها از میله‌ی دوم هم می‌توانیم کمک بگیریم ولی هیچ گاه اجازه نداریم صفحه‌ای را روی صفحه‌ی کوچک‌تر قرار بدهیم.

تعداد جا به جایی‌های لازم برای n صفحه را h_n می‌نامیم و خیلی ساده فکر می‌کنیم. برای پیدا کردن h_n فرض می‌کنیم بلد هستیم n-1 صفحه را جا به جا کنیم و تعداد جا به جایی‌های لازم برای این کار را h_n-1 می‌نامیم. اکنون کار را تمام می‌کنیم. در آغاز فرض می‌کنیم با h_n-1 جا به جایی n-1 صفحه‌ی بالایی را به میله‌ی ۲ برده‌ایم و احتمالا در این کار از میله‌ی سوم نیز کمک گرفته‌ایم. سپس به سادگی بزرگ‌ترین صفحه را از میله‌ی نخست به میله‌ی سوم می‌بریم و بالاخره n-1 میله را دوباره با h_n-1 جا به جایی به میله‌ی سوم می‌بریم و احتمالا در این کار از میله‌ی نخست نیز کمک می‌گیریم.
بنا بر این مقدار h_n را چنین به دست آورده‌ایم:

h_n=2h_n-1+ 1

اما به سادگی روشن است که برای جا به جایی تنها یک صفحه نیاز به یک جا به جایی داریم. پس داریم:

h₁= 1

و به کمک رابطه‌ای که پیدا کرده بودیم می‌توانیم برای nهای بزرگ‌تر از ۱ چنین محاسبه کنیم:

h₂= 3, h₃= 7, h₄= 15, h₅= 31, ...

حالا شما دست به کار شوید و این مساله را حل کنید:


نادر می‌خواهد از ده پله بالا برود. او می‌تواند در هر گام یک پله یا دو پله یا حداکثر سه پله بالا برود. نادر به چند روش می‌تواند از این ده پله بالا برود؟