Question: 2014 Fall Midterm - 9

Let $m \geq 1$ and $n \geq 1$ be integers. Consider a rectangle whose horizontal side has length $m$ and whose vertical side has length $n$. A path from the bottom-left corner to the top-right corner is called valid, if in each step, it either goes one unit to the right or one unit upwards.

In the example below, you see a valid path for the case when $m = 5$ and $n = 3$. How many valid paths are there?

a) ${m + n \choose n - 1}$

b) ${m + n \choose n}$

c) $2^{m + n}$

d) $2^m + 2^n$

Let $m \geq 1$ and $n \geq 1$ be integers. Consider a rectangle whose horizontal side has length $m$ and whose vertical side has length $n$. A path from the bottom-left corner to the top-right corner is called valid, if in each step, it either goes one unit to the right or one unit upwards.
In the example below, you see a valid path for the case when $m = 5$ and $n = 3$. How many valid paths are there?

(a)

$2^{m + n}$

(b)

${m + n \choose n}$

(c)

$2^m + 2^n$

(d)

${m + n \choose n - 1}$