calculating total number of allowable paths from $(0,0)$ to $(5,5)$ 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? 
 A: 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*}

                                             
A: 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.
A: 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)
