سوال ۴

جدولی $n \times n$ داریم که سطرهای آن از بالا به پایین و ستون‌های آن از چپ به راست با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند. خانه‌ی واقع در سطر $i$ و ستون $j$ را با $(i, j)$ نشان می‌دهیم. می‌خواهیم از خانه‌ی $(1,1)$ به خانه‌ی $(n,n)$ برویم. حرکت‌های مجاز به صورت زیر هستند:

• حرکت از $(i,j)$ به $(i+1,j)$ با هزینه‌ی $j$.
• حرکت از $(i,j)$ به $(i,j+1)$ با هزینه‌ی $i$.

چند مسیر مجاز دارای کم‌ترین هزینه هستند؟

1. $\binom{2n-2}{n-1}$
2. $\binom{2n}{n}$
3. 2
4. $n$
5. $\frac{1}{2}\binom{2n}{n}$

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