سوال ۵

می‌خواهیم $n$ ماتریس $M_1$ تا $M_n$ را در هم ضرب کنیم ($M=M_1\times M_2 \times … \times M_n$). فرض کنید ابعاد ماتریس‌ها به گونه‌ای هستند که حاصلضرب هر دو ماتریس مجاور امکان‌پذیر است می‌خواهیم تعداد ترتیب‌های مختلف برای انجام این ضرب را به دست آوریم. این ترتیب‌ها را می‌توان با استفاده از پرانتز نشان داد. فرض کنید $T_n$ تعداد حالات پرانتزگذاری این ضرب باشد. مثلا $T_4=5$ و ترتیب‌های مورد نظر بقرار زیرند:

$$M_1 \times ((M_2\times (M_3 \times M_4)) \\ M_1 \times ((M_2\times M_3) \times M_4) \\ (M_1 \times M_2)\times (M_3 \times M_4) \\ (M_1 \times (M_2\times M_3)) \times M_4 \\ ((M_1 \times M_2)\times M_3 )\times M_4$$

الف) فرمولی برای $T_n$ بر حسب $T_i$ ها $(i<n)$‌ بنویسید و آن را اثبات کنید.

ب) برنامه‌ای بنویسید تا با دریافت $n$،‌ $T_n$ را در خروجی چاپ نماید.

• سوال بعد
• سوال قبل