Combinatorics: How many possible paths?

Question

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!

Answer 1

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

Answer 2

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

Answer 3

I found that when I do the question in the view of Combinations, it's frustrating. But when I do the question from the view of Generalized Permutation (Orderings with Repetitions), which is:

We're ordering of $S$ with $n$ items, with $n_1$ of type 1, $n_2$ of type 2, ..., $n_t$ of type $t$. So the result will just be: $$\frac{n!}{n_1! \cdot n_2! \cdot \dots \cdot n_t!}$$

It's natural to find that we're ordering 7 moves, 4 of them Right, 3 Up, so $\frac{7!}{4!3!}$ is what we'll get.

Answer 4

Did you try Pascal's triangle?

$1 \space 1$
$1 \space 2 \space 1$
$1 \space 3 \space 3 \space 1$
$1 \space 4 \space 6 \space 4 \space 1$
$1 \space 5 \space 10 \space 10 \space 5 1$
$1 \space 6 \space 15 \space 20 \space 15 \space 6 \space 1$
$1 \space 7 \space 21 \space 35 \space 35 \space 21 \space 7 \space 1$

$^7C_4 = 35$

How many ways can we add up to $7$? What is the coefficient of $u^3l^4$, where $u$ is up and $l$ is left.

Answer 5

One has to select 4 right steps and 3 up steps out of 7 total steps. So, using multinomial rules as discussed by @Key Flex.

Number of ways = $\frac{7!}{4!\times 3!}$ = 35