Imagine a two-dimensional grid consisting of 20 points along the x-axis and 10 points along the y-axis. Suppose the origin (0,0) is in the bottom-left corner and the point (20,10) is the top-right corner. A path on the grid consists of a series of moves in which each move is either one unit to the right or one unit up. Diagonal moves are not allowed. How many different ways are there to construct a path starting at (0,0) and ending at (20,10)?

I'm a little stuck on this one. I feel I'm headed towards the right direction, but I'm not sure if I'm doing this right. For every move, there are 2 possible choices. If we want to get to (20,10), then there are 200 points from the origin to this point. And I think order matters here, so we would use permutations, so I come up with 200 P 2, which is 39,800.

  • 3
    $\begingroup$ Just a quick comment: if you have 20 points along the $x$ axis, and the bottom left is at coordinates $(0,0)$, then presumably the bottom right is at coordinates $(19,0)$, not $(20,0)$ (count them!); likewise for $y$. So with 20 points along the x-axis and 10 along the y-axis, the top-right corner should be at $(19,9)$, not at $(20,10)$. If so, you need to adjust the discussions in the answers. $\endgroup$ – Arturo Magidin Nov 27 '10 at 23:10
  • $\begingroup$ For higher dimensions this is just the multinomial coefficent $\endgroup$ – Albas Feb 16 '16 at 12:49

You have 30 moves to make, 10 of which must be up and 20 of which must be right. How many ways to pick which are the 10?

  • $\begingroup$ What do you mean by how many ways to pick which are the 10? So we would have a sum of combinations? 10 choose 2? $\endgroup$ – Snowman Nov 27 '10 at 18:37
  • $\begingroup$ If you start with a plan of 30 right moves, you will wind up at (30,0). If you change one of those moves to up, you will wind up at (29,1). Keeping at it, if you change 10 moves to up, you wind up at (20,10). But you can change any 10 of the 30 and achieve this result. How many ways are there to select which ones to change? $\endgroup$ – Ross Millikan Nov 27 '10 at 18:41
  • $\begingroup$ Oh I see, so 30 choose 10? I'm not sure if order matters. I dont think it would, as long as you make the move. $\endgroup$ – Snowman Nov 27 '10 at 18:45
  • $\begingroup$ No, order doesn't matter. Try it for 2 and 2, which you can solve by hand. So yes it is 30 choose 10 $\endgroup$ – Ross Millikan Nov 27 '10 at 18:50
  • $\begingroup$ I've seen a version of this question that does not restrict the movements to only up and right (but you cant retrace your steps). Is there a way of calculating the number of unique paths in that case? The only methods I could come up with required a computer to solve by going through all the valid permutations. $\endgroup$ – Ralth Nov 27 '10 at 19:34

There are two ways of doing this. One is Ross Millikan's: you will make ten "up" moves, and 20 "right" moves; the only question is which order you make them in. Imagine placing the "right" moves on a row; now you need to decide where to do the "up" moves: you do so by inserting them "in between" (or before, or after) the "right" moves. So you need to choose ten places to put "up" moves: there are 21 locations for them (nineteeen in between the "right" moves, one before all of them, one after), and you are allowed to choose the same location more than once.

This is a combinations-with-repetitions: the formula is $\binom{n+r-1}{r}$, where you have $n$ possibilities, and must make $r$ choices with repetitions allowed. In this case, $n=21$, $r=10$, so you get $\binom{30}{10}$.

There is another way of doing it, which is more graphical. I'll do it with a 4 by 3 array so you see how it works. You have this array: $$\begin{array}{cccc} \cdot & \cdot & \cdot & \cdot\\ \cdot & \cdot & \cdot & \cdot\\ \cdot & \cdot & \cdot & \cdot \end{array}$$ Now, you start at the bottom left, so there is only one way to get there; we put a $1$ next to it. $$\begin{array}{llll} \cdot & \cdot & \cdot & \cdot\\ \cdot & \cdot & \cdot & \cdot\\ \cdot\;1& \cdot & \cdot & \cdot \end{array}$$ Then, you can go either up or right; there is only one way to get to those points (via the first move); we put a $1$ next to them: $$\begin{array}{llll} \cdot & \cdot & \cdot & \cdot\\ \cdot\;1 & \cdot & \cdot & \cdot\\ \cdot\;1& \cdot\;1 & \cdot & \cdot \end{array}$$ Now: to get to $(1,1)$, you can either get to it from $(1,0)$ or from $(0,1)$; since there is only one way to get to each of those, there are two ways to get to $(1,1)$. On the other hand, only one way to get to $(2,0)$ or to $(0,2)$: $$\begin{array}{llll} \cdot\;1 & \cdot & \cdot & \cdot\\ \cdot\;1 & \cdot\;2 & \cdot & \cdot\\ \cdot\;1& \cdot\;1 & \cdot\;1 & \cdot \end{array}$$ Next: to get to $(1,2)$, you can arrive either from $(0,2)$ (one way of being there), or from $(1,1)$ (two ways of getting there); so in total, three ways. Likewise, you have three ways to get to $(2,1)$, because you can either go up from $(2,0)$, and there is only one way to do all of that, or you can go right from $(1,1)$ (and there are two ways of doing that, corresponding to the two ways there are to get to $(1,1)$; so we have: $$\begin{array}{llll} \cdot \;1 &\cdot\;3 & \cdot & \cdot\\ \cdot\;1 & \cdot\;2 & \cdot\;3 & \cdot\\ \cdot\;1& \cdot\;1 & \cdot\;1 & \cdot \end{array}$$ Continuing this way, we get: $$\begin{array}{llll} \cdot\;1 & \cdot\;3 & \cdot\;6 & \cdot\;10\\ \cdot\;1 & \cdot\;2 & \cdot\;3 & \cdot\;4\\ \cdot\;1 & \cdot\;1 & \cdot\;1 & \cdot\;1 \end{array}$$ So there are $10$ ways to get to the top right corner in the 4 by 3 case.

You may even recognize that these numbers are just Pascal's triangle lying on its side! Well, there is a combinatorial formula for the entries of Pascal's triangle: the $r$th entry in the $m$th row corresponds to the coefficient of $a^{m-r}b^{r-1}$ in the binomial expansion of $(a+b)^{m-1}$, so it equals $\binom{m-1}{r-1}$. To figure out the entry that corresponds to the top right corner, note that you go "down" one row for each position on the $x$-axis, and another one for each step up. So here we have gone to the 4th row on the horizontal steps, and then to the 6th row on the by going up twice. Each step up is a move "right" on the row. So with a 4 by 3, we are in row $4+(3-1)=6$, and we are in position $3$ of that row. According to the formula above, that corresponds to $\binom{4+2-1}{3-1}=\binom{5}{2}$. This corresponds to the need to make $3$ moves right and two moves up, so we need choose where to place the two up moves among the three right moves; there are four places to put them in (before the three, after the three, or in the two spaces in between), so the formula I gave above gives this answer as well.

  • 1
    $\begingroup$ Nice explanation, thanks! $\endgroup$ – Snowman Nov 27 '10 at 19:12
  • 1
    $\begingroup$ Yeah, this is great Arturo! Thanks much, an awesome explanation! $\endgroup$ – Relative0 Jul 19 '13 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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