Let n > 0 and m > 0 be integers. Consider an n X m rectangle as shown in figure.

Question

Let n > 0 and m > 0 be integers. Consider an n X m rectangle as shown in figure. We are interested in finding paths between the point A = (0.0) and B = (n,m). A path starts at A = (0,0) and in each step, we are allowed to move one unit either in -fx-direction or in +y-direction, till we reach B = (n. m). Such type of paths are called monotone paths. (Examples of two such paths are shown in bold in the figure.) Note that any monotone path is composed of exactly n unit horizontal segments and m unit vertical segments. How many monotone paths are there from A to 5? Justify your answer.

Explanation / Answer

Ans: m+n C n or m+n C m. (m+n combination n or m+n combination m)

We need to move n steps in horizontal direction and m steps in vertical direction. Hence, we have total m+n steps. Hence to reach at point (n,m) we need to move n+m steps. Out of these steps we need to choose n steps or m steps from m+n steps. We can choose any of the n steps from n+m steps. Hence the number of paths is equal to m+n choose n or m+n choose m.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.