Back

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$

Solution: 2014 Fall Midterm - 9

Author: Michiel Smid

Question

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}$

Solution

We can check the first few cases to see which answer matches the pattern:

$m=1, n=1: 2$
$m=2, n=2: 6$

If we now plug in these values into the answers we are given for $m=1, n=1$:

$\binom{m+n}{n-1} = \binom{1+1}{1-1} = \binom{2}{0} = 1$
$\binom{m+n}{n} = \binom{1+1}{1} = \binom{2}{1} = 2$
$2^{m+n} = 2^{1+1} = 2^{2} = 4$
$2^{m} + 2^{n} = 2^{1} + 2^{1} = 2 + 2 = 4$

As you can see, the only answer that works is b).