Question

به چند طریق می توان جدول $3 \times 10$ را با موزاییک های $1 \times 2$ پوشاند ؟

Comments

از دنباله های بازگشتی استفاده کنیذ و سپس ان را حل کنید.

Answer 1

یک سری تصویر پسین‌تر خواهم‌افزود.

یک مستطیل با عرض ۳ و طول ۱۰ در نظر بگیرید. از سمت چپ شروع می‌کنیم به فرش کردن آن با مستطیل‌های یک در دو. سه حالت برای ردیف آخر بیشتر وجود ندارد یا یک مستطیل افقی بالا و یک مستطیل عمودی زیرش، یا سه مستطیل افقی، یا یک مستطیل عمودی بالا و یک مستطیل افقی در زیر. حالت دوم ما را به فرش کردن مسطتیل با عرض ۳ و طول ۸ کاهش می‌دهد. حالت یکم (به تقارن حالت سوم نیز مشابه می‌شود تنها با یک تقارن) شما رو به دو حالت می‌کشاند یا اینکه یک مستطیل عمودی دیگر در کنار مستطیل عمودی پائین قرار می‌دهید و دوباره به حالت فرش کردن یک مستطیل $3\times 8$ می‌‌رویم، یا اینکه دو تا مستطیل افقی در کنار مستطیل عمودی پائین می‌گذاریم. در این صورت مجبور می‌شویم گوشهٔ $1\times 1$ بالای سمت راست را باید با یک مستطیل افقی پر کنیم. آن وقت دوباره به دو راهی پیشین می‌رسیم. در اینصورت چیزی که رُخ داده‌است این است که اگر تعداد حالت‌های فرض کردن مستطیل $3\times 2n$ با مستطیل‌های $1\times 2$ را با $f(n)$ نشان دهیم، داریم: $$f(n)=f(n-1)+2\sum_{i=1}^{n-1}f(i)$$ روشن است که دستی می‌توان دید که $f(1)=3$ و $f(2)=11$.

اگر می‌خواهید شکل فرمول ساده‌تر شود می‌توانید محاسبات زیر را انجام دهید. $$\begin{array}{l} f(n)=3f(n-1)+2\sum_{i=1}^{n-2}f(i)\\ f(n-1)=f(n-2)+2\sum_{i=1}^{n-2}f(i)\\ 2\sum_{i=1}^{n-2}f(i)=f(n-1)-f(n-2)\\ \Longrightarrow f(n)=3f(n-1)+f(n-1)-f(n-2)\\ f(n)=4f(n-1)-f(n-2) \end{array}$$ بنابراین برای رابطهٔ بازگشتی نیاز به دو مقدار آغازین هستید. می‌توانید $n=1$ و $n=2$ را بردارید یا اینکه قرارداد کنید که $f(0)=1$ و دو مقدار $n=0$ و $n=1$ را بردارید. توجه کنید که برای فرمول پیشین فقط یک مقدار آغازین نیاز داشتید، و حتما نیاز به برداشتنِ $f(0)=1$ داشتید و گرنه فرمول عدد کمتری را به شما خواهد داد. علت شهودی آن نیز دقیقا همان علت شهودیِ قرار دادنِ $\binom{m}{0}=1$ است.

خواستهٔ پرسش، $f(5)$ است که می‌توانید خودتان حساب کنید.