1

The diagram below shows a $4$ rows $\times$ $6$ columns grid. Find the number of ways to travel from $A$ (at the bottom left) to the top right along the grid lines. At every junction point, one can only go right or upwards.

enter image description here

I can setup a tree diagram and then count (slowly) the total number of routes. The question is how to arrive at the elegant answer : $\binom{8}{3}$.

Bérénice
  • 9,367
Mick
  • 17,141
  • 1
    Well to get to your destination you need 3 Up moves and 5 Right moves, so a total of 8 moves. Now is the basic combinatorial interpretation of $C(8,3)? Is that enough for you to see the answer? – almagest Apr 23 '16 at 19:09
  • @almagest Yes. You have explained the "8", but what about the "3" (or "5")? – Mick Apr 23 '16 at 19:13
  • 3 Up moves (and 5 Right moves). You are choosing 3 of your 8 moves as Up moves. – almagest Apr 23 '16 at 19:15

2 Answers2

5

A standard way of looking at this problem is as follows. Each step you take is either an $U$ for up or an $R$ for right. Notice that whatever you do, you'll need to move $5$ times to the right and $3$ times up to get from the bottom left to the top right corner. So a route corresponds to an $8$ letter long word made of $3$ $U$ letters and $5$ $R$ letters. Also each such word corresponds to a good route.

Therefore it's enough to count these words. And there are exactly $\binom {8}{5} = \binom{8}{3}$ of these, since out of the $8$ places you have to choose $5$ where you put the letter $R$ - or equivalently out of the $8$ places choose the $3$ where you put the letter $U$.

Eman Yalpsid
  • 3,044
  • As a curiosity, C(n, r) is used to calculate the number of combinations of taking r objects from a total of n. In this application, we have used it with an extra detail of “the remaining n – r objects will be handled automatically”. Is that correct? – Mick Apr 23 '16 at 19:34
  • By selecting $r$ objects from n objects, you are also selecting the other $(n-r)$ objects by 'not selecting' them. In this specific problem you are selecting all of the places where you go up, but -since you can only go up or right- doing so you are also selecting the places where you go right. – Eman Yalpsid Apr 23 '16 at 19:40
2

This problem is known as Lattice path : https://en.wikipedia.org/wiki/Lattice_path.

We have the result that the number of lattice paths from $(0,0)$ to $(a,b)$ is : $$\binom{a+b}{a}$$ So here the answer is indeed $\binom{8}{3}$.

You can obtain this result by induction : The previous step to reach $(a,b)$ is $(a-1,b)$ or $(a,b-1)$ so by hypothesis of induction and by using some properties of binomial coefficients you can prove the result... (Tell me if you encounter some problemsin the proof by induction).

Bérénice
  • 9,367
  • I have no problem in the induction part, Glad to learn something new - the Lattice path. – Mick Apr 23 '16 at 19:16