0
$\begingroup$

Starting at the point $(0,0)$ how many ways are there to get to the point $(7,4)$ if you have to pass through the point $(1,1)$ and each step can only be one unit to the right or one unit up.

$\endgroup$

closed as off-topic by Namaste, TravisJ, Lee David Chung Lin, Misha Lavrov, max_zorn Jan 26 at 22:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, TravisJ, Lee David Chung Lin, max_zorn
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 12
    $\begingroup$ How many paths from $(0,0)$ to $(1,1)$? How many from $(1,1)$ to $(7,4)$? $\endgroup$ – lulu Jan 24 at 20:58
  • 2
    $\begingroup$ Please be aware, Keshav, that posting too many posts in a short period of time that receive downvotes, are closed, or are deleted, including your deletion of downvoted posts, puts you in jeopardy of losing the privilege to post questions. $\endgroup$ – Namaste Jan 25 at 17:30
  • 2
    $\begingroup$ Possible duplicate of Counting number of moves on a grid $\endgroup$ – Larry B. Jan 25 at 20:44
0
$\begingroup$

From $(0,0)$ to $(1,1)$ there are only two ways. Then, for the remaining path, the question is equivalent to asking how many paths are there from $(0,0)$ to $(6,3)$.

The way to think about this problem is by means of the binomial expansion. First, notice that you always need $6+3$ steps to reach your goal, no matter the path. Consider then the square defined by the points $(0,0)$ and $(6+3,6+3)=(9,9)$.

If you think of the grid as a tree (there are no cycles because of your 'up-right rule'), it becomes clear that, in order to reach end point $i$ you have $\binom{9}{i}$ different paths. In your case, your end point is $(6,3)$, thus $$ \binom{9}{6}=\binom{9}{3}=84. $$ Hence, the final answer is $84\times 2=168$.

This reasoning is useful because it yields the answer for the number of paths between $(0,0)$ and any point $(n,m)$, with your 'up-right' restriction. Simply take $$ \binom{n+m}{n}. $$

$\endgroup$
2
$\begingroup$

There are two ways to get from $(0,0)$ to $(1,1)$. (One path goes through $(1,0)$ the other through $(0,1)$).

Once you are at $(1,1)$, you ought to look at how many ways there are to get from $(1, 1)$ to $(7, 4)$.

You could draw out the grid and write down the number of possible ways to get to each point along a potential path:

For example, starting at $(1,1)$, there is $1$ way to get to $(1, 2)$ and there is also one way to get to $(2, 1)$. The number of ways to get to any particular point is the sum of the number of ways to get to the point immediately to the left of or below that point.

You can also do some combinatorics: To get from $(1,1)$ to $(7,4)$ you must go right $6$ units and up $3$ units. That's a total of $9$ steps. The number of ways to get from $(1,1)$ to $(7,4)$ is the number of unique ways the $6$ rights and $3$ ups can be arranged.

$C(9,3) = C(9, 6) = \frac {9!} {6! 3!} = \frac { 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 } { 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 3 \cdot 2 \cdot 1} = \frac{ 9 \cdot 8 \cdot 7} {3 \cdot 2 \cdot 1} = \frac {504} {6} = 84$

There are $84$ ways to get from $(1,1)$ to $(7,4)$. Multiplying this by the two ways to get from $(0, 0)$ to $(1, 1)$ gives you $168$ ways to get from $(0,0)$ to $(7,4)$ passing through $(1,1)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.