Question

• به چند طریق می توان با 3n مهره دو مینو یک جدول $3×2n$ پوشاند. خیلی سعی کردم حداقل یک رابطه بازگشتی بدست آورم.

• می دونم که برای حل جدول $2×n$ ، فرض می کنیم که به $a_n$ طریق بتوان این کار انجام داد، چند جمله اول بدست می آوریم: $a_1=1,\quad a_2=2,\quad a_3=3,..... $ برای $n>2 $ به دو صورت مجزا زیر می توان جدول پوشاند

• یا یک مهره آخر به صورت عمودی است که در این صورت بقیه جدول به $a_{n-1}$ طریق می توان پوشاند

• یا دو مهره آخر افقی است که در این حالت به $a_{n-2}$ بنابراین به دنباله بازگشتی زیر می رسیم $$a_n=a_{n-1}+a_{n-2}$$ این رابطه باز گشتی می توان حل کرد یا با مقایسه دنباله فیبوناچی داریم: $$a_n=f_{n+1}$$

Answer 1

سلام. سه تابع مختلف تعریف میکنیم و با کمک اونها مسئله رو حل میکنیم

تابع اول را $A(n)$ مینامیم که برابر است با تعداد روش های پرکردن جدول 32n با دومینو(همان جواب مسئله اصلی). تابع دوم را $B(n)$ مینامیم که برابر است با تعداد روش های پرکردن یک جدول 2n3 با دومینو با این تفاوت که خانه بالای آخرین ستون آن جدول خالی است. تابع سوم را $C(n)$ مینامیم که برابر است با تعداد روش های پرکردن یک جدول 2n*3 با دومینو به طوری که خانه پایین آخرین ستون آن خالی است. عکس زیر به صورت دقیق توابع گفته شده را نشان میدهد

حال آخرین ستون از جدول 2n*3 را در نظر میگیریم و بررسی میکنیم که دومینو هارا به چه صورت میتوانیم قرار دهیم. با اندکی بررسی متوجه میشویم حالات زیر محتمل است :

طبق شکل خواهیم داشت : $A(n) = A(n - 2) + B(n - 1) + C(n - 1)$ برای راحت تر شدن کار در حل رابطه بازگشتی میتوانیم کمی رابطه را ساده تر کنیم. میتوانیم بجای 3 متغیر از دو متغیر استفاده کنیم. در شکل بالا واضح است که $B(n) = C(n)$ میباشد و لازم نیست جداگانه آنهارا حساب کنیم. کافیست یکی از آنهارا حساب کرده و ضربدر دو کنیم. پس خواهیم داشت : $A(n) = A(n - 2) + 2B(n - 1) $

پس

$B(n) = A(n) + B(n−1)$

با حل رابطه بازگشتی خواهیم داشت :

$A(n+1) = 4A(n) − A(n−1)$

Comments

1@ArtinDrdمتوجه نتیجه گیری چند خط شما نشدم ضمنا جواب معادله باز گشتی بدست آورید؟
به نظرم رابطه آخر درست نیست چون اگر n زوج باشه A(n) وجود دارد و یک مقدار طبیعی است اما A(n-1) برابر صفر است بنابراین تساوی خط آخر درست نیست.