$m\times n$ squares, how many ways exist to get from the top-left corner to the bottom-right corner if you can only move right or down on an edge?
-
- 16 tennis players participate in a doubles tournament and are paired at random. How many ways are there to select a pair?
- How many different ways can a football team’s manager choose 5 penalty takers from 11 players?
-
How many steps in total must be taken?
-
From a total of
$m+n$steps, how many are rightward steps and how many are downward steps? -
If we have
$m$rightward steps, how many combinations of them are there? -
For each combination of rightward steps, how many combinations of downward steps are there?
-
Regardless of the path taken, you must travel
$m$steps right and$n$steps down, i.e. you must always travel$m+n$steps. Of these, we consider the number of different ways we may choose$m$to be rightward steps. This is$\binom{m+n}{m}=\frac{(m+n)!}{n!m!}$. For each of these combinations, the remaining$n$steps down are uniquely determined i.e. there is only 1 combination since$\binom{m+n-m}{n} = \binom{n}{n} = 1$, so$\binom{m+n}{m}$is our final answer.Similarly, we may first find the combinations of
$n$downward steps and fix rightward steps to obtain$\binom{m+n}{n}$as our answer.Another way to look at this is to consider the permutations of
$m+n$steps, where$m$rightward steps and$n$downward steps are both indistinguishable types of steps. We find the number of permutations for$m+n$things, and remove (by dividing by) the number of permutations specifically for just the rightwards and downward steps. This gives us the answer$\frac{(m+n)!}{m! \cdot n!}$.