calculating total number of allowable paths from $(0,0)$ to $(5,5)$

Question

I'm looking at paths starting from $(0,0)$ with the following allowable steps :

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

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

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

how can I determine the total number of paths from $(0,0)$ to $(5,5)$?

and then generally from $(0,0)$ to $(n,n)$ using the same allowable steps. Is it possible to do this using binomial theorem?

Answer 1

We algebraically encode the base steps \begin{align*} &(1,0)\qquad\to\qquad x\\ &(0,1)\qquad\to\qquad y\\ &(2,1)\qquad\to\qquad x^2y \end{align*} so that each step can be encoded as $(x+y+x^2y)$. Denoting the coefficient of $x^n$ with the coefficient of operator $[x^n]$ we want to find \begin{align*} [x^5y^5]\sum_{q=0}^\infty(x+y+x^2y)^q\tag{1} \end{align*} which means we consider paths of length $q\geq 0$ and for each path we get the number of possibilities from $(0,0)$ to $(5,5)$ and sum up all these numbers.

We obtain from (1) \begin{align*} \color{blue}{[x^5y^5]}&\color{blue}{\sum_{q=0}^\infty\left(x+y+x^2y\right)^q}\\ &=[x^5y^5]\sum_{q=0}^\infty \sum_{{j+k+l=q}\atop{j,k,l\geq0}}\binom{q}{j,k,l}x^jy^k\left(x^2y\right)^l\tag{2}\\ &=[x^5y^5]\sum_{q=0}^\infty \sum_{{j+k+l=q}\atop{j,k,l\geq0}}\binom{q}{j,k,l}x^{j+2l}y^{k+l}\\ &=[x^5]\sum_{q=0}^\infty\sum_{k=0}^5\sum_{{j+k+(5-k)=q}\atop{j\geq 0}}\binom{q}{j,k,5-k}x^{j+10-2k}\tag{3}\\ &=[x^5]\sum_{q=0}^\infty\sum_{k=3}^5\binom{q}{q-5,k,5-k}x^{q+5-2k}\tag{4}\\ &=\binom{6}{1,3,2}+\binom{8}{3,4,1}+\binom{10}{5,5,0}\tag{5}\\ &=\frac{6!}{1!3!2!}+\frac{8!}{3!4!1!}+\frac{10!}{5!5!0!}\\ &\,\,\color{blue}{=592} \end{align*}

Comment:

• In (2) we expand the trinomial using multinomial coefficients.

• In (3) we select the coefficient of $y^5$ by setting $k=0,\ldots,5$ and $l=5-k$.

• In (4) we set the lower limit of $k$ to $3$ since $x^{j+10-2k}$ has exponent less than $5$ otherwise. The index relation in (3) also shows that $j+5=q$ and we eliminate $j$.

• In (5) we select the coefficient of $x^5$.

The steps $x+y+x^2y$ indicate a recurrence relation \begin{align*} a_{m,n}&=a_{m-1,n}+a_{m,n-1}+a_{m-2,n-1}\qquad\ m\geq 2,n\geq 1\\ a_{m,0}&=1=a_{0,n}\qquad\qquad\qquad\qquad\qquad\quad m,n\geq 0\\ a_{1,n}&=n\qquad\qquad\qquad\qquad\qquad\qquad\qquad n\geq 1 \end{align*} Some values of the recurrence relation are listed in the table below, which verifies the solution \begin{align*} \color{blue}{a_{5,5}}&=a_{4,5}+a_{5,4}+a_{3,4}=241+296+55\color{blue}{=592} \end{align*}

                                             

Answer 2

It is the coefficient $x^5y^5$ in the generating function \begin{eqnarray*} \frac{1}{1-x-y-x^2 y}. \end{eqnarray*} For a value as small as $(5,5)$ it is probably easiest to just calculate the grid of values by hand. It is like calculating pascal's triangle but with the extra value that is $2$ back & $1$ down, added.

Answer 3

By just using condition 1 and 2 we have 2^n solutions. The third condition could be used n-3 times. Hence total no of ways is 2^n*(n-3)