calculating total number of allowable paths

Question

I seem to be struggling with the following type of path questions

Consider paths starting at $(0, 0)$ with allowable steps

(i) from $(x,y)$ to $(x+1,y+2)$,

(ii) from $(x,y)$ to $(x+2,y+1)$,

(iii)from $(x,y)$ to $(x+1,y)$

Determine the total number of allowable paths from $(0, 0)$ to $(8, 8)$, and the total number of allowable paths from $(0, 0)$ to $(10, 10)$.

I dont know how to go about this question.

could anyone recommend a trivial method to tackle problems of these types in an exam setting?

Answer 1

Draw a table and think backwards. Let $p(x,y)$ be the number of such paths from $(0,0)$ to $(x,y)$. By conditioning on the last step into $(x,y)$, we find that $$p(x,y)=p(x-1,y-2)+p(x-2,y-1)+p(x-1,y),$$ where $p(x,y)=0$ if $x<0$ or $y<0$. You know that $p(0,0)=1$, and you want to compute $p(8,8)$ and $p(10,10)$. The resulting table is \begin{matrix} x\backslash y &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 \\ \hline 0 &1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ 1 &1 &0 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\ 2 &1 &1 &2 &0 &1 &0 &0 &0 &0 &0 &0 \\ 3 &1 &2 &3 &2 &3 &0 &1 &0 &0 &0 &0 \\ 4 &1 &3 &5 &6 &6 &3 &4 &0 &1 &0 &0 \\ 5 &1 & &8 &12 &13 &12 &10 &4 &5 &0 &1 \\ 6 & & &12 & &27 &30 &26 &20 &15 &5 &6 \\ 7 & & & & &51 & &65 &60 &45 &30 &21 \\ 8 & & & & & & &146 & &\color{red}{130} &105 &71 \\ 9 & & & & & & & & &336 & &231 \\ 10 & & & & & & & & & & &\color{red}{672} \\ \end{matrix} In particular, $$p(8,8) = p(7,6)+p(6,7)+p(7,8) = 65+20+45=130.$$

Answer 2

Suppose you do $A$ moves of type (i), $B$ of type (ii) and $C$ of type (iii). If you want to reach $(8, 8)$, then clearly $A + 2B + C = 8$ and $2A + B = 8$. This yields $B = 8-2A$ and $C = 3A - 8$. Since $A, B, C$ are nonnegative integers, you obtain solutions $(A, B, C) = (3, 2, 1)$ or $(4, 0, 4)$.

Now to calculate paths, for $(4, 0, 4)$ case, a path is described by string of four $A$s and four $C$s. For example, $AAACCACC$ is one such path. There is ${8 \choose 4} = 70$ such paths.

For the $(3, 2, 1)$ case there is ${6 \choose 3} \cdot 3 = 60$ such paths. Altogether there are $130$ such paths.

For reaching $(10, 10)$ same logic gives you $B = 10 - 2A$ and $C = 3A - 10$, so solutions are $(4, 2, 2)$ and $(5, 0, 5)$.

So, the number of paths is ${8 \choose 4} {4 \choose 2} + {10 \choose 5} = 70 \cdot 6 + 252 = 672$.

This is in agreement with Rob Pratts answer. Also, I would like to emphasise as I did in the comment that his answer is "better" in a sense that it illustrates how you can handle any problem of this type, since his answers scales reasonably to larger numbers. This answer can from the practical point of view only be used on such a small examples. But, if I was writing an exam, I'd take this approach (or at least I would try and then estimate would it be faster done this way or in the more general way)