Moving from $(0,0)$ to $(5,5)$ without right angles

Generating function approach.

Let $H(x,y)$, $V(x,y)$ and $D(x,y)$ be the generating functions of the paths which ends at $(n,m)$ with an horizontal step, a vertical step, or a diagonal step respectively.

Then the following linear relations hold $$\begin{cases} H=x(H+D)\\ V=y(V+D)\\ D-1=xy(H+V+D) \end{cases} $$ By solving the system, we find that the generating function of all the paths is $$F(x,y)=H(x,y)+V(x,y)+D(x,y)=\frac{1-xy}{1-x-y+x^2y^2}.$$ Hence the number of paths from the origin to $(n,n)$ for $n\geq 0$ is $$[x^ny^n]\frac{1-xy}{1-x-y+x^2y^2}=1, 1, 3, 9, 27, 83, 259, 817, 2599, 8323, 26797,\dots.$$ Therefore, for $n=5$, the answer is $83$.

The sequence appears in OEIS as A171155 and, according to the references, the diagonal of $F(x,y)$ is $$\sqrt{\frac{1-x}{1-3x-x^2-x^3}}.$$


If I understand the problem correctly, and you let $\ n_h(x,y)\ $ be the number of paths from $\ (0,0)\ $ to $\ (x,y)\ $ with final step horizontal from $\ (x-1,y)\ $, $\ n_v(x,y)\ $ the number with final step vertical from $\ (x,y-1)\ $, and $\ n_d(x,y)\ $ the number with final step diagonal from $\ (x-1,y-1)\ $ then $\ n_h, n_v, n_d\ $ must satisfy the following recursions \begin{align} n_h(x,y)&=n_h(x-1,y)+n_d(x-1,y)\\ n_v(x,y)&=n_v(x,y-1)+ n_d(x,y-1)\\ n_d(x,y)&=n_h(x-1,y-1)+ n_v(x-1,y-1)+n_d(x-1,y-1) \end{align} for $\ 1\le x,y\le5\ $, and the following initial conditons \begin{align} n_h(x,0)&=1, n_v(x,0)=n_d(x,0)=0\ \text{ for }\ 1\le x\le5\ ,\\ n_v(0,y)&=1, n_h(0,y)=n_d(0,y)=0 \ \text{ for }\ 1\le y\le5,\ \text{and}\\ n_v(1,1)&=n_h(1,1)=0, n_d(1,1)=1\ . \end{align} Applying these recursions to the initial conditions we get the values of $\ n_h(x,y), n_v(x,y), n_d(x,y)\ $ given in the following table: \begin{array}{c|cccccc} {}_y\backslash{}^x&0&1&2&3&4&5\\ \hline 0&&(1,0,0) &(1,0,0) &(1,0,0) &(1,0,0) &(1,0,0)\\ 1&(0,1,0) & (0,0,1)&(1,0,1)&(2,0,1)&(3,0,1)&(4,0,1)\\ 2 &(0,1,0)&(0,1,1)&(1,1,1)&(2,1,2)&(4,1,3)&(7,1,4)\\ 3& (0,1,0) &(0,2,1)&(1,2,2)&(3,3,3)&(6,4,5)&(11,5,8)\\ 4 &(0,1,0) &(0,3,1)&(1,4,3)&(4,6,5)&(9,9,9)&(18,13,15)\\ 5 &(0,1,0) &(0,4,1)&(1,7,4)&(5,11,8)&(13,18,15)&(28,28,27) \end{array} The total numbet of paths from $\ (0,0)\ $ to $\ (5,5)\ $ is therefore $\ n_h(5,5)+n_v(5,5)+n_d(5,5)=$$28+28+27=83\ $.