گراف زیر چند مسیر از $A$ به $B$ دارد؟ توجه کنید یک مسیر نمیتواند رأس یا یال تکراری داشته باشد.
پاسخ
گزینهی ۵ درست است.
رئوس را به شکل زیر شمارهگذاری میکنیم:
$g_n$
را تعداد مسیرهای از رأس
$n$
به $B$ تعریف میکنیم، طوری که از گام به صورت
$\leftarrow$
استفاده نشود. پاسخ در انتها برابر $g_9$
خواهد بود. با کمی بررسی متوجّه میشویم:
$$g_n = g_{n-1} + g_{n-2} + g_{n-3}$$
حال از آنجایی که
$g_0=1$،
$g_1=1$
و
$g_2=2$
داریم:
$$g_3 = 4 \Rightarrow g_4 = 7 \Rightarrow g_5 = 13 \Rightarrow g_6 = 24 \Rightarrow g_7 = 44 \Rightarrow g_8=81 \Rightarrow g_9 = 149$$
پس پاسخ برابر ۱۴۹ است.