در سوال قبل، به چند طریق میتوانیم مهره را از خانهی پایین-چپ به خانهی بالا-راست برسانیم، طوری که از هر خانه حداکثر یک بار عبور کنیم؟
پاسخ
گزینهی ۳ درست است.
تعداد روشهای رسیدن از خانهی پایین-چپ به خانهی بالا-راست در یک جدول 2×n را an و تعداد روشهای رسیدن از خانهی بالا-چپ به خانهی بالا-راست در همین جدول را bn در نظر میگیریم. با حالتبندی روی گام نخست، روابط بازگشتی زیر را داریم: an=2an−1+2bn−1+2an−2+2bn−2bn=2an−1+2bn−1+2an−2+2bn−2 از آنجایی که a1=1a2=5b1=1b2=5 مقدار a5=560 به دست میآید.