# Combinatorics: How many possible paths?

Consider the following grid.

We start at the bottom left corner. We may only move one step up or one step right at each move. This procedure is continued until we reach the top right corner. How many different paths from the bottom left corner to the top right corner are possible?

This is an excerise from Sheldon Ross' A First Course in Probability.

The correct answer is $$\binom{7}{4}=35.$$ However, no explanation is given. I understand that there are $7$ moves total that must be made: $$3\ \text{steps up and}\ 4\ \text{steps to the right.}$$ Can anyone provide me with an explanation of how the author came up with this answer?

Thanks so much!

• You can describe a path as a list of seven symbols, each with four Rs and three Us, for up and right. Like URRURUR. Of the 7 symbols, 4 must be chosen to be R, hence $\binom74$. – Mike Earnest Jun 23 '18 at 21:07
• Thank you! That makes a lot of sense because $\binom{7}{3}$ also equals $35.$ – MathIsLife12 Jun 23 '18 at 21:09

What Mike Earnest said is simpler, but here's a strategy that also applies, for example, for 3-D paths.

Note that the number of paths is equal to the number of ordered 7-tuples with 3 $U$'s and 4 $R$'s, for example $URRURRU$ means, in order, go up, right, right, up, right, right, up.

The number of these is $$\frac{\# \text{ways to order 7 different letters}}{\# \text{ways to re-order the equivalent U's} \cdot \# \text{ways to re-order the equivalent R's}} = \frac{7!}{3! \cdot 4!} = \binom{7}{4}.$$

Now, starting at the point $A$, we can go one step to the right and one step to the up at each move. This procedure is continued until the point labeled $B$ is reached.

To reach $B$ from $A$, $4$ steps are to be taken to the right and $3$ steps up.

So, the total number of steps taken to reach $B$ from $A$ is $7$.

Let the total number of steps be $m=7$

Let the steps to the right be $n_1=4$

Let the steps to the upward be $n_2=3$

So, to find the possible number of paths from $A$ to $B$

use the multinomial rule, the possible number of paths from $A$ to $B$ is $$\frac{m!}{n_1!\times n_2!}=\frac{7!}{4!\times 3!}$$

$$=\frac{7\times 6 \times 5 \times 4!}{4!\times 3 \times 2\times 1}=35$$

So, the number of paths from $A$ to $B$ is $35$ ways.

• You meant steps up rather than steps to the left. – N. F. Taussig Jun 23 '18 at 21:16
• Thanks, I fixed it. – Key Flex Jun 23 '18 at 21:20